# US 2014/0208327 A1 · Method for simultaneous scheduling of processes and offloading computation on many-core coprocessors

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

- Number: US 2014/0208327 A1
- Document ID: US20140208327A1
- Status: Published application
- Kind: A1
- Application number: 13/858,039
- Filed: 2013-04-06
- Published: 2014-07-24
- Earliest claimed: 2013-01-18
- Assignees: NEC Laboratories America, Inc.
- Applicants: NEC Laboratories America, Inc.
- Inventors: Srihari Cadambi; Kunal Rao; Srimat T. Chakradhar; Rajat Phull; Giuseppe Coviello; Murugan Sankaradass; Cheng-Hong Li
- Web page: https://patentgrep.com/patent/US20140208327A1

## CPC

- G06F 9/5044: {considering hardware capabilities}
- G06F 9/5033: {considering data affinity}
- G06F 2209/509: Offload
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method is disclosed to manage a multi-processor system with one or more manycore devices, by managing real-time bag-of-tasks applications for a cluster, wherein each task runs on a single server node, and uses the offload programming model, and wherein each task has a deadline and three specific resource requirements: total processing time, a certain number of manycore devices and peak memory on each device; when a new task arrives, querying each node scheduler to determine which node can best accept the task and each node scheduler responds with an estimated completion time and a confidence level, wherein the node schedulers use an urgency-based heuristic to schedule each task and its offloads; responding to an accept/reject query phase, wherein the cluster scheduler send the task requirements to each node and queries if the node can accept the task with an estimated completion time and confidence level; and scheduling tasks and offloads using a aging and urgency-based heuristic, wherein the aging guarantees fairness, and the urgency prioritizes tasks and offloads so that maximal deadlines are met.

## Claims

### Claim 1

A method for scheduling workload in a system with a server node and one or more manycore coprocessors, comprising:
receiving requests from processes or offloads to the coprocessors, each process or offload requesting a predetermined quality of service (QoS) including a request for memory and threads for a specified duration;
determining a fit function, which determines the eligibility of a process or offload if one of the coprocessors has sufficient memory to satisfy a process' QoS and sufficient memory and threads to satisfy an offload's QoS;
determining an urgency function for scheduling an offload or a process; and
selecting a process from a process list and an offload from an offload list based on the fit function and the urgency function.

### Claim 2 (depends on 1)

The method of claim 1, comprising simultaneous scheduling processes and offloads.

### Claim 3 (depends on 1)

The method of claim 1, comprising deducting credits associated with a process if the process overruns resource consumption and otherwise adding credits to the process if the process uses less resources than planned.

### Claim 4 (depends on 1)

The method of claim 1, comprising using credits to prioritize a process or to relax the accuracy with which a user has to specify task processing times.

### Claim 5 (depends on 1)

The method of claim 1, wherein the urgency function is determined based on the process or offload's priority, age, waiting time, QoS and credit for freeing resource(s) ahead of requested processing time for each resource.

### Claim 6 (depends on 1)

The method of claim 1, comprising assigning an urgency to a process an offload, where the urgency is a function of age, priority, arrival time, credits and QoS of a process or an offload.

### Claim 7 (depends on 1)

The method of claim 1, comprising using urgency to prioritize a process or offload, wherein the urgency depends on deadlines and processing times and is used to prioritize tasks and offloads so that maximal deadlines are met.

### Claim 8 (depends on 1)

The method of claim 1, comprising aging a process and offload.

### Claim 9 (depends on 1)

The method of claim 1, comprising blocking scheduling depending on age.

### Claim 10 (depends on 1)

The method of claim 1, comprising allowing controlled memory and thread oversubscription using a configuration parameter.

### Claim 11

A method to manage a multi-server cluster with each server containing one or more coprocessors, comprising:
managing real-time bag-of-tasks applications for a cluster, wherein each task runs on a single server node, and uses the offload programming model, and wherein each task has a deadline and three specific resource requirements: total processing time, a certain number of manycore devices and peak memory on each device;
when a new task arrives, querying each node scheduler to determine which node can best accept the task and each node scheduler responds with an estimated completion time and a confidence level, wherein the node schedulers use an urgency-based heuristic to schedule each task and its offloads;
responding to an accept/reject query phase, wherein the cluster scheduler send the task requirements to each node and queries if the node can accept the task with an estimated completion time and confidence level; and
scheduling tasks and offloads using a aging and urgency-based heuristic, wherein the aging guarantees fairness, and the urgency prioritizes tasks and offloads so that maximal deadlines are met.

### Claim 12 (depends on 11)

The method of claim 11, comprising applying an aging-based first-fit for process and offload scheduling.

### Claim 13 (depends on 11)

The method of claim 11, comprising applying thread and memory over-scheduling factors to enhance performance.

### Claim 14 (depends on 11)

The method of claim 11, comprising applying greedy core selection such that offloads from the same process get preference to use the same cores.

### Claim 15

A scheduler, comprising;
a computer with a server with one or more manycore processors;
a cluster scheduler; and
one or more node schedulers, wherein for a task, the cluster scheduler queries each node scheduler to determine which node accepts the task, wherein each node scheduler responds with an estimated completion time and a confidence level.

### Claim 16 (depends on 15)

The scheduler of claim 15, wherein the node schedulers use an urgency-based heuristic to schedule each task and its offloads.

### Claim 17 (depends on 16)

The scheduler of claim 16, wherein the heuristic uses deadlines and predicted estimates of the number of future offloads and execution times.

### Claim 18 (depends on 15)

The scheduler of claim 15, wherein the scheduler uses one or more credits to relax an accuracy with which users have to specify processing times.

### Claim 19 (depends on 18)

The scheduler of claim 18, wherein the credits allow the scheduler to amortize task overruns across tasks of a user.

### Claim 20 (depends on 15)

The scheduler of claim 15, wherein the node scheduler's estimators allow the cluster scheduler to quickly refuse infeasible tasks.

### Claim 21 (depends on 15)

The method of claim 15, wherein the server node performs providing an Accept/Reject query phase and sending task requirements to each node when a task with a deadline and resource requirements arrives at a cluster of coprocessor nodes and queries if the node accepts the task, wherein the nodes indicate acceptance of the task with an estimated completion time and a confidence level.
