Scheduler and scheduling method for reconfigurable architecture
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/46
G06F-015/78
G06F-009/48
출원번호
US-0197591
(2014-03-05)
등록번호
US-9311270
(2016-04-12)
우선권정보
KR-10-2013-0023492 (2013-03-05)
발명자
/ 주소
Kim, Won-Sub
Choi, Yoonseo
Park, Hae-Woo
출원인 / 주소
Samsung Electronics Co., Ltd.
대리인 / 주소
NSIP Law
인용정보
피인용 횟수 :
0인용 특허 :
3
초록▼
A scheduler and scheduling method perform scheduling for a reconfigurable architecture. The scheduling, performed by the scheduler, includes path information extracting including extracting direct path information and indirect path information between functional units in a reconfigurable array compl
A scheduler and scheduling method perform scheduling for a reconfigurable architecture. The scheduling, performed by the scheduler, includes path information extracting including extracting direct path information and indirect path information between functional units in a reconfigurable array complying with predefined architecture requirements, based on architecture information of the reconfigurable array, command selecting including selecting a command from a data flow graph (DFG) showing commands to be executed by the reconfigurable array, and scheduling including scheduling the selected command based on the extracted direct path information and indirect path information.
대표청구항▼
1. A scheduler for a reconfigurable architecture comprising: a path information hardware processor configured to extract direct path information and indirect path information between functional units in a reconfigurable array complying with predefined architecture requirements, based on architecture
1. A scheduler for a reconfigurable architecture comprising: a path information hardware processor configured to extract direct path information and indirect path information between functional units in a reconfigurable array complying with predefined architecture requirements, based on architecture information of the reconfigurable array;a command hardware processor configured to select a command from a data flow graph (DFG) representing commands to be executed by the reconfigurable array; anda scheduling hardware processor configured to schedule the selected command based on the extracted direct path information and indirect path information,wherein the scheduling hardware processor is configured to search for a direct path between two functional units at which the selected command and a command, which has a data dependency with respect to the selected command, are, respectively, placed, based on the direct path information, and, if the search for a direct path search fails search for an indirect path between the two functional units based on the indirect path information. 2. The scheduler of claim 1, wherein the reconfigurable array is a coarse grained reconfigurable array. 3. The scheduler of claim 1, wherein the predefined architecture requirements comprise that at least one indirect path is present between every two functional units in the reconfigurable array, and that a direct path is present between at least one pair of functional units of the reconfigurable array, and the reconfigurable array complies with at least one of the predefined architecture requirements. 4. The scheduler of claim 1, wherein the scheduling hardware processor is further configured to comprise: a placement validity checking device configured to search for a functional unit and a time that are available for placement of the selected command;a command placement device configured to place the selected command at the functional unit and time found;a routing path searching device configured to search for a routing path between the placed command and a command which has a data dependency with respect to the placed command, based on the direct path information and indirect path information; anda validity determining device configured to determine validity of the found routing path by checking an occupancy state of a node on the routing path. 5. The scheduler of claim 4, wherein the validity determining device is configured to, when there is a node exclusively connected to either a source node or a destination node on the found routing path, check an occupancy state of remaining nodes on the routing path, other than the exclusively connected node, to determine the validity of the found routing path. 6. A scheduling method for reconfigurable architecture comprising: extracting, at a path information hardware processor, direct path information and indirect path information between functional units in a reconfigurable array complying with predefined architecture requirements, based on architecture information of the reconfigurable array;selecting, at a command hardware processor, a command from a data flow graph (DFG) representing commands to be executed by the reconfigurable array; andscheduling, at a scheduling hardware processor, the selected command based on the extracted direct path information and indirect path information,wherein the scheduling of the selected command comprises, searching for a direct path between two functional units at which the selected command and a command, which has a data dependency with respect to the selected command, are, respectively, placed, based on the direct path information, andif the search for a direct path search fails, searching for an indirect path between the two functional units based on the indirect path information. 7. The scheduling method of claim 6, wherein the reconfigurable array is a coarse grained reconfigurable array. 8. The scheduling method of claim 6, wherein the predefined architecture requirements comprise that at least one indirect path is present between every two functional units in the reconfigurable array, and that a direct path is present between at least one pair of functional units of the reconfigurable array, and the reconfigurable array complies with at least one of the predefined architecture requirements. 9. The scheduling method of claim 6, wherein the scheduling of the selected command further comprises: searching for a functional unit and a time that are available for placement of the selected command;placing the selected command at the functional unit and time found;searching for a routing path between the placed command and a command which has a data dependency with respect to the placed command, based on the direct path information and indirect path information; anddetermining validity of the found routing path by checking an occupancy state of a node on the routing path. 10. The searching method of claim 9, wherein the determining of the validity of the routing path comprises, when there is a node exclusively connected to either a source node or a destination node on the found routing path, checking an occupancy state of remaining nodes on the routing path, other than the exclusively connected node, to determine the validity of the routing path found. 11. A reconfigurable architecture comprising: functional units in a reconfigurable array complying with predefined architecture requirements, based on architecture information of the reconfigurable array, configured to: provide direct path information and indirect path information between the functional units to a scheduler; and receive a scheduled command scheduled by the scheduler based on the direct path information and the indirect path information, wherein the scheduler is further configured to search for a direct path between two functional units at which the selected command and a command, which has a data dependency with respect to the selected command, are, respectively, placed, based on the direct path information, and, if the search for a direct path search fails, search for an indirect path between the two functional units based on the indirect path information. 12. The reconfigurable architecture of claim 11, wherein the scheduled command is selected from a data flow graph (DFG) representing commands to be executed by the reconfigurable array. 13. The reconfigurable architecture of claim 11, wherein the reconfigurable array is a coarse grained reconfigurable array. 14. The reconfigurable architecture of claim 11, wherein the predefined architecture requirements comprise that at least one indirect path is present between every two functional units in the reconfigurable array, and that a direct path is present between at least one pair of functional units of the reconfigurable array, and the reconfigurable array complies with at least one of the predefined architecture requirements. 15. The reconfigurable architecture of claim 11, wherein the reconfigurable architecture is further configured to receive scheduling information for the scheduled command scheduled by the scheduler. 16. The reconfigurable architecture of claim 15, wherein the scheduling information comprises an ordered pair including a functional unit identifier and a time. 17. The reconfigurable architecture of claim 16, wherein the reconfigurable architecture is further configured to execute the scheduled command at the functional unit and time corresponding to the scheduling information.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (3)
Ramchandran, Amit, Adaptable datapath for a digital processing system.
Arimilli, Lakshminarayana B.; Arimilli, Ravi K.; Rajamony, Ramakrishnan, System and method for dynamically supporting indirect routing within a multi-tiered full-graph interconnect architecture.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.