Scheduler for a fine grained graph processor

• US 9,984,037 B1
• Filed: 04/27/2016
• Issued: 05/29/2018
• Est. Priority Date: 04/27/2015
• Status: Active Grant

• Current Assignee: Xceler Systems Inc.
• Original Assignee: Synaptic Engines, Llc
• Inventors: Kavipurapu, Gautam
• Primary Examiner(s): Das, Chameli
• Application Number:
  US15/139,529
• Time in Patent Office: 762 Days
• Field of Search: 717161
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A novel scheduler design is provided that schedules a set of operations to an array of similar or dissimilar, candidate operations on a cycle by cycle basis, out of a total number of operations. The array of similar or dissimilar units can be atomic in nature or ALU like or complete processors. The scheduler is able to map the operations in a data flow/sequencing graph to the two dimensional or 3 dimensional array (which can be extended to a multi-dimensional array) optimally so as to minimize the total execution times. The mapping is path based computation, where a particular sequence of instructions is routed through the underlying matrix in path that minimized the number of memory hops.

Claims

1. A method for scheduling a task for a fine grained graph processor, the method operated by a scheduler in a fine grained graph processor based system and comprising:

i. scheduling nodes of a same label field within a set of nodes of an unscheduled sequencing graph for execution by said fine grained graph processor within a same execution time slot to form a scheduled sequencing graph, wherein;

(1) said fine grained graph processor includes a matrix of execution units interconnected by port blocks and a global switched memory, wherein said matrix includes planes of execution units and said planes are interconnected by said global switched memory, and wherein each execution unit of said matrix includes a broadcast switch element, a receive switch element, or a memory element;

(2) said unscheduled sequencing graph is generated from a task coded in a computer programming language; and

(3) said unscheduled sequencing graph includes said set of nodes indicating a set of instructions of said task, each node within said set of nodes including a label field that indicates a distance between nodes of said unscheduled sequencing graph; and

ii. during each scheduling cycle, checking for availability of a least expensive execution path and required execution units for executing instructions of said scheduled sequencing graph within a corresponding execution time slot by determining a first status of execution units of said fine grained graph processor, and a second status of an execution unit scoreboard.

2. The method for scheduling a task of claim 1 further comprising scheduling nodes farthest from an end of said unscheduled sequencing graph first for execution by said fine grained graph processor.

3. The method for scheduling a task of claim 1 further comprising performing lookups of a linearized array of said execution units represented by said execution resource scoreboard to generate an execution scoreboard, said execution scoreboard including a set of execution scoreboard entries, each entry within said set of execution scoreboard entries including values of execution unit types, entry numbers of execution unit types, a status, a scheduling cycle, co-ordinates of corresponding execution units within said matrix, wherein said execution scoreboard is updated during each scheduling cycle.

4. The method for scheduling a task of claim 1 wherein said schedule checks for said availability of a least expensive execution path and required execution units by

i. firstly checking execution units of a same row of a same plane within said matrix;

ii. secondly checking execution units of different rows of a same plane within said matrix; and

iii. thirdly checking execution units of different planes within said matrix.

5. The method for scheduling a task of claim 1 wherein said schedule includes:

i. a sequencing graph space adapted to store said unscheduled sequencing graph;

ii. an unscheduled ops block including unscheduled instructions;

iii. a candidate ops block including unscheduled instructions that have a largest label field value;

iv. a scheduling ops block including instructions for which required execution units are available in a given execution cycle; and

v. controller block adapted to control operation of said scheduler.

6. The method for scheduling a task of claim 5 wherein said schedule is implemented as a computer software.

7. The method for scheduling a task of claim 5 wherein said schedule is implemented as a computer hardware.

8. The method for scheduling a task of claim 5 wherein said schedule is implemented as a combination of both computer hardware and computer software.

9. The method for scheduling a task of claim 1 further comprising generating said unscheduled sequencing graph by:

vi. compiling said task into an op-code set;

vii. replacing each register of said op-code set with a port block register or a location within said global switched memory of said fine grained graph processor; and

viii. consolidating data load for said unscheduled sequencing graph.

10. The method for scheduling a task of claim 9 further comprising:

i. profiling said task to generate instruction statistics; and

ii. determining an amount of required resources of said fine grained graph processor for executing said task.

11. The method for scheduling a task of claim 10 further binding a global variable of said task to said global switched memory.

12. The method for scheduling a task of claim 10 further associating a local variable of said task with a port block of said find grained graph processor, wherein said local variable is intended to be left in place in an execution context.