Resource sharing aware task partitioning for multiprocessors

• US 8,938,739 B2
• Filed: 06/02/2012
• Issued: 01/20/2015
• Est. Priority Date: 06/02/2012
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Lee, Sejoong, Choi, Soon-Hyeok, Kandhalu Raghu, Arvind
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Huaracha, Willy W
• Application Number:
  US13/487,185
• Publication Number:
  US 20130326523A1
• Time in Patent Office: 962 Days
• Field of Search: 718/102, 718/103, 718/105
• 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 not combined tasks 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 a 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 determined by using the following equation;

2. 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 not combined tasks 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 a 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 is determined by using the following equation;

3. 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 not combined tasks 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 a 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 is determined by using the following equation;

4. The method of claim 3 wherein:

the recursive equation is converted into a convergence equation;