# US 2019/0171497 A1 · Accelerated Operation of a Graph Streaming Processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171497 A1
- Document ID: US20190171497A1
- Status: Published application
- Kind: A1
- Application number: 16/270,766
- Filed: 2019-02-08
- Published: 2019-06-06
- Earliest claimed: 2015-05-26
- Assignees: ThinCl, Inc.
- Applicants: ThinCI, Inc.
- Inventors: Lokesh Agarwal; Sarvendra Govindammagari; Venkata Ganapathi Puppala; Satyaki Koneru
- Web page: https://patentgrep.com/patent/US20190171497A1

## CPC

- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/3877: {using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12)}
- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/903: Querying (for retrieval from the web G06F16/953)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods, systems and apparatuses for graph processing are disclosed. One graph streaming processor includes a thread manager, wherein the thread manager is operative to dispatch operation of the plurality of threads of a plurality of thread processors before dependencies of the dependent threads have been resolved, maintain a scorecard of operation of the plurality of threads of the plurality of thread processors, and provide an indication to at least one of the plurality of thread processors when a dependency between the at least one of the plurality of threads that a request has or has not been satisfied. Further, a producer thread provides a response to the dependency when the dependency has been satisfied, and each of the plurality of thread processors is operative to provide processing updates to the thread manager, and provide queries to the thread manager upon reaching a dependency.

## Claims

### Claim 1

A graph streaming processor,
the graph streaming processor operative to process a plurality of threads of a plurality of thread processors, wherein each thread includes a set of instructions operating on the plurality of thread processors and operating on a set of data and producing output data, wherein processing of at least one of the threads is dependent upon processing of another of the plurality of threads, wherein the plurality of threads include producer threads and dependent threads, wherein producer threads produces data for dependent threads and dependent threads consume data produced by producer threads;
the graph streaming processor comprising a thread manager, the thread manager comprising a plurality of stages and a one of a plurality of command buffers located between each of pairs of the plurality of stages, wherein each stage includes physical hardware operative to schedule each of the threads, including an input command buffer parser operative to interpret commands within a corresponding input command buffer and generate the plurality of threads, wherein the thread manager is operative to:
dispatch operation of the plurality of threads of the plurality of thread processors before dependencies of the dependent threads have been resolved;
maintain a scorecard of operation of the plurality of threads of the plurality of thread processors;
provide an indication to at least one of the plurality of thread processors when a dependency between the at least one of the plurality of threads that a request has or has not been satisfied;
wherein a producer thread provides a status indication when the dependency has been satisfied;
wherein the plurality of thread processors is operative to:
provide processing updates to the thread manager; and
provide queries to the thread manager upon reaching a dependency.

### Claim 2 (depends on 1)

The graph streaming processor of claim 1, wherein the graph streaming processor includes a first mode of operation and a second mode of operation, wherein for the first mode of operation the thread manager is operative to dispatch operation of the plurality of threads before dependencies of the dependent threads have been resolved, and for a second mode of operation, the thread manager is operative to dispatch operation of the plurality of threads of the plurality of thread processors after dependencies of the dependent threads have been resolved.

### Claim 3 (depends on 2)

The graph streaming processor of claim 2, wherein a dependent thread and a consumer thread include a common code block operating on different data, and further comprising selecting the graph streaming processor to operate in the first mode if the dependency of the consumer thread occurs within a selected number of instructions from the end of the consumer thread.

### Claim 4 (depends on 2)

The graph streaming processor of claim 2, wherein a dependent thread and a consumer thread include a common code block operating on different data, and further comprising selecting the graph streaming processor to operate in the second mode if the dependency of the consumer thread occurs within a selected number of instructions from the start of the consumer thread.

### Claim 5 (depends on 2)

The graph streaming processor of claim 2, further comprising selecting the graph streaming processor to operate in the first mode when a producer thread and a consumer thread each include a different code block.

### Claim 6 (depends on 1)

The processor of claim 1, wherein each of the thread processors is further operative to:
periodically provide queries to check for resolution of the dependency between the thread of the thread processor and at least one of the producer threads.

### Claim 7 (depends on 1)

The processor of claim 1, wherein each of the thread processors is further operative to:
provide a completion of execution indicator to the thread manager upon completing execution of the thread of the thread processor.

### Claim 8 (depends on 1)

The processor of claim 1, wherein maintaining the scorecard comprises maintaining an indication of the status of the plurality of threads including statuses of dependencies between producer threads and dependency threads.

### Claim 9 (depends on 1)

The processor of claim 1, wherein thread processors of consumer threads check for completion of dependencies by thread processors of producer threads, and continue processing of the consumer threads upon resolution of the dependencies.

### Claim 10 (depends on 1)

The processor of claim 1, wherein the thread manager continues to dispatch threads as long as at least one of the plurality of thread processors is available regardless of whether dependencies of the dispatched threads have been resolved.

### Claim 11

A method of graph steaming processing, comprising:
processing, by a graph streaming processor, a plurality of threads, wherein each thread includes a set of instructions operating on the plurality of thread processors and operating on a set of data and producing output data, wherein processing of at least one of the threads is dependent upon processing of another of the plurality of threads, wherein the plurality of threads include producer threads and dependent threads, wherein producer threads produces data for dependent threads and dependent threads consume data produced by producer threads;
wherein the graph streaming processor includes a thread manager, wherein the thread manager includes a plurality of stages and a one of a plurality of command buffers located between each of pairs of the plurality of stages, wherein each stage includes physical hardware operative to schedule each of the threads, including an input command buffer parser operative to interpret commands within a corresponding input command buffer and generate the plurality of threads;
the graph steaming processing further including;
dispatching, by the thread manager of the graph streaming processor, operation of the plurality of threads of the plurality of thread processors before dependencies of the dependent threads have been resolved;
maintaining, by the thread manager, a scorecard of operation of the plurality of threads of the plurality of thread processors;
providing, by the thread manager, an indication to at least one of the plurality of thread processors when a dependency between the at least one of the plurality of threads that a request has or has not been satisfied;
wherein a producer thread provides a response to the dependency when the dependency has been satisfied:
providing, by each of the plurality of thread processors, processing updates to the thread manager;
providing, by the plurality of thread processors, queries to the thread manager upon reaching a dependency.

### Claim 12 (depends on 11)

The method of claim 11, further comprising:
dispatching, by the thread manager, operation of the plurality of threads before dependencies of the dependent threads have been resolved for a first mode of operation of the graph streaming processor;
dispatching, by the thread manager, operation of the plurality of threads of the plurality of thread processors after dependencies of the dependent threads have been resolved for a second mode of operation of the graph streaming processor.

### Claim 13 (depends on 12)

The method of claim 12, wherein a dependent thread and a consumer thread include a common code block operating on different data, and further comprising:
selecting the graph streaming processor to operate in the first mode if the dependency of the consumer thread occurs within a selected number of instructions from the end of the consumer thread.

### Claim 14 (depends on 12)

The method of claim 12, wherein a dependent thread and a consumer thread include a common code block operating on different data, and further comprising: selecting the graph streaming processor to operate in the second mode if the dependency of the consumer thread occurs within a selected number of instructions from the start of the consumer thread.

### Claim 15 (depends on 12)

The method of claim 12, further comprising selecting the graph streaming processor to operate in the first mode when a producer thread and a consumer thread each include a different code block.

### Claim 16 (depends on 11)

The method of claim 11, further comprising:
periodically providing, by the thread processors, queries to check for resolution of the dependency between the thread of the thread processor and at least one of the producer threads.

### Claim 17 (depends on 11)

The method of claim 11, further comprising:
providing, by the thread processors, a completion of execution indicator to the thread manager upon completing execution of the thread of the thread processor.

### Claim 18 (depends on 11)

The method of claim 11, wherein maintaining the scorecard comprises maintaining an indication of the status of the plurality of threads including statuses of dependencies between producer threads and dependency threads.

### Claim 19 (depends on 11)

The method of claim 11, wherein thread processors of consumer threads check for completion of dependencies by thread processors of producer threads, and continue processing of the consumer threads upon resolution of the dependencies.

### Claim 20 (depends on 11)

The method of claim 11, wherein the thread manager continues to dispatch threads as long as at least one of the plurality of thread processors is available regardless of whether dependencies of the dispatched threads have been resolved.
