Resource Sharing Aware Task Partitioning for Multiprocessors

• US 20130326523A1
• Filed: 06/02/2012
• Published: 12/05/2013
• Est. Priority Date: 06/02/2012
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Raghu, Arvind Kandhalu, Lee, Sejoong, Choi, Soon-Hyeok
• Granted Patent: US 8,938,739 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: 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

Abstract

A multi processor task allocation method is described that considers task dependencies while performing task allocation in order to avoid blocking of a task'"'"'s execution while waiting for the resolution of the dependency. While allocating the tasks to the processors the potential blocking time is considered, and the best allocation that will have the least amount of blocking time is found.

Claims

1. A method of multiprocessor task partitioning comprising the steps of:

calculating processor utilization for each task;

combining tasks sharing a common resource to form composite tasks;

calculating processor utilization for each composite task;

arranging the independent and the composite tasks in a non increasing order of their processor utilization in an array;

applying a worst fit decreasing heuristic on the tasks in said array;

using the response time test for the schedulability on each composite task;

if the schedulability test does not pass for a composite task;

determining the various breaking cost for the composite task by calculating the remote blocking term B^r; and

breaking the composite task with the lowest B^r.

2. The method of claim 1 wherein:

the remote blocking term B^r is determined by using the following equation;

3. The method of claim 1 wherein:

the remote blocking term B^r is determined by using the following equation;

4. The method of claim 1 wherein:

the remote blocking term B^r is determined by using the following equation;

5. The method of claim 2 wherein:

the said recursive equation is converted into a convergence equation;