Highly efficient scheduler for a fine grained graph processor

Abstract

A highly efficient method for scheduling operations to be performed by a fine grained graph processor is performed by a fine gained graph processor based system. The method first determines a set of execution paths for executing a sequence of operations. Each path logically passes through a set of execution units of the fine grained graph processor. The execution units are interconnected by BSEs and RSEs, each of which includes one or more memory elements. The method also determines availability of each execution path within the set by determining availability of execution units of the path. The checking of availability of execution units checks from one execution unit to another in the same row first, one execution unit to another in different rows on the same plane secondly and then one execution unit to another in different planes. The method is designed to reduce execution cost.

What is claimed is: 
     
         1 - 15 . (canceled) 
     
     
         16 . An efficient method for scheduling an operation to be performed by a fine grained graph processor, the method performed by a scheduler running on a fine grained graph processor based system and comprising:
 determining a set of execution paths, wherein:
 (1) each execution path within said set of execution paths includes a sequence of operations; 
 (2) said sequence of operations includes said operation; 
 (3) each execution path within said set of execution paths passes through execution units of said fine grained graph processor that perform atomic operations; and 
 (4) said fine grained graph processor includes a set of planes of execution units interconnected by port blocks and a global switched memory, execution units of each plane within said set of plane arranged in rows and columns, execution units of said fine grained graph processor interconnected via broad cast switch elements and receive switch elements, said broad cast switch elements and receive switch elements each including a memory element; and 
   ii. determining availability of each execution path within said set of execution paths by determining availability of execution units of said execution path for executing said operation, wherein said availability of execution units is determined by:
 (1) firstly checking availability of execution units in a same row; 
 (2) secondly checking availability of execution units in a different rows within a same plane; and 
 (3) thirdly checking availability of execution units in a different planes.