FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
PROVISIONAL SPECIFICATION
(See Section 10 and Rule 13)
Title of the invention: METHOD OF REORGANIZING TASKS FOR OPTIMIZATION OF RESOURCES


Applicant; KPIT Cummins Infosystems Limited
35 and 36, Rajiv Gandhi Infotech Park
Phase 1, MIDC, Hinjawadi
Pune-411 057
Maharashtra, India

FIELD OF THE INVENTION
The present invention relates generally to the field of task management & resource optimization and, more particularly, to scheduling of tasks for execution in an environment comprising multiple processing elements.
BACKGROUND OF THE INVENTION
Computer programs include a plurality of tasks that are executed in a particular sequence and time determined by logic of the corresponding source code and constraints of the processing hardware used. Computer systems and, in particular, ones incorporating multiple processing elements can achieve faster execution of these computer programs and yet be rational in their demand for processing hardware resources provided they incorporate a method that is efficient in synchronization, scheduling and dispatching for execution of the tasks that comprise said computer programs. Devising such a method, tailor-made for multiple processing environments, has been the focus of research for the present inventors.
BRIEF DESCRIPTION OF THE INVENTION
The method for scheduling tasks according to the principles of the present invention involves a multitude of steps. The first step involves mapping of tasks to be executed. Mapping involves qualitative and quantitative assessment of various functional elements and variables contained within the time frame for execution of said tasks. Thus, the step of mapping reveals characteristics of the subject tasks in accordance to its original execution, including the execution times of individual tasks, sequence of execution, interdependency of the tasks and the schematics of release of downstream tasks as a result of execution of upstream tasks.
The second step of the method for scheduling tasks is to represent the data obtained from the mapping step in terms of a matrix of dimensions NxN where N is the total number of tasks. Depending on the task dependencies and other chronometric data represented in the said matrix, decisions are made as to scheduling of the tasks. Example 1 illustrates use of the test dependency matrix in scheduling of tasks in a computer program.
Example 1
Consider a hypothetical computer application containing 7 tasks having data as represented in Table 1.

Task ID
(Tid) Task
execution
time
(Tx) Number of
Dependent
Tasks
(NDT) List of
Dependent
Tasks
(LDT) Wait time
for
releasing
tasks
(Tw) Start time
(relative to
individual
processor)
(Ts) Elapsed time
for
corresponding
processor
(Te) Task
Status
Flag
(SF)
1 2 100 200 2
0 2,3 None 60,30 0 0 0 0 NS NS

0

3 30 3 4,6,7 10,20,25 0 0 0 0 NS NS NS
4
5 90 1 5 60 50

100 1 6
0 0

6 250 0 None 0 0 0 NS
7 150 0 None 0 0 0 NS
TABLE 1: DATA FOR SUBJECT CODE FOR TIME = 0
Where,
1) Tid i.e the task ID is the nomenclature used for naming the tasks in the subject application.
2) Tx is the time required for execution of corresponding task
NDT is the number of tasks the execution of which can be initiated only after starting the execution of the corresponding task. While assigning priority to a task due consideration will be given to the number of dependent tasks being released by the particular task
3) LDT is the list of task IDs which get released during execution of the corresponding task
4) Tw is the time required into the execution of the particular releaser task until which execution of the corresponding task cannot be initiated
5) Ts is the absolute time, on the real-time scale, at which the task starts its execution. This time is relative to the first resource on which the first task is scheduled
6) Te is the total time elapsed, on the real-time scale, at that instance of time. This time is corresponds to the time elapsed for the resource on which the task is scheduled
7) SF is the flag for status of the task having following values:

a) S -> task scheduled or execution initiated
b) NS -> task not scheduled yet
c) C -> execution of task is complete
I

Now, the task dependency matrix for the subject program would be as illustrated in table 2

Aij T1 T2 T3 T4 T5 T6 T7
0
0 25
T1 0 60 30 0 0 0 0 0 20

T2 0 0 0 0

T3 T4 0 0 0 0 0 0 10 0

0 60 0 50 0 0
T5 0 0 0 0 0

T6 0 0 0 0 0 0 0
T7 0 0 0 0 0 0 0
TABLE 2: TASK DEPENDENCY RELEASE MATRIX (TDM) = A[N][N]
Where,
1) A[i][j] = indicates the wait time for 'j'th task to start execution, after 7th task has started
executing, i.e. the dependency of 'j'th task on 7th task is over when 7th task runs for time
AMD].
2) A[j][i] = indicates the wait time for task 'j' to start executing after start of 7th task
Having determined the dependency of the tasks, it is an objective of the present invention to achieve logical dispatch of the tasks to individual processing elements to realize the full potential of the multiple processing elements.
Mapping of the available multiple processing elements is the next step towards deriving the logic of scheduling available tasks for processing on said processing environment. Starting with the assumption of having single processor, the same logic leads to the determination of optimal number of processors for fastest practical execution of the subject code. For this, a real time-updated Processor Status Table (PST) is maintained, more particularly represented as table 3
I

Processor List of Start time Completion Processor
ID Scheduled for time for Availability
Tasks scheduled tasks on scheduled task on real Time
(Pid) (LT) real time time scale
scale (Ts) (Tc) (PAT)
1 1 0 100 0



TABLE 3: PROCESSOR STATUS SHEET AT TIME = 0
Where,
1) Pid is the nomenclature used for identifying the individual processing element
2) LT is the list of tasks scheduled to be run on the corresponding processor
3) Ts is the time for initiation of execution of corresponding tasks. This time is on the real time scale i.e. it is the absolute time w.r.t. zero
4) Tc is the time required for completion of execution of corresponding tasks. This time is on the real time scale i.e. it is the absolute time w.r.t. zero. It is equal to the sum of the start time and the execution time of the corresponding task.
5) PAT is the time remaining for the processor element to be free and thus, available for accepting further tasks for processing. In other words, it is the time remaining for the task to complete its execution on the assigned resource

S

Task ID
(Tid) Task
execution
time
(Tx) Number of
Dependent
Tasks
(NDT) List of
Dependent
Tasks
(LDT) Wait time
for
releasing
tasks
(Tw) 60,30 Start time
(Ts) Elapsed time
for
corresponding
processor
(Te) Task
Status
Flag
(SF)
1 2 100 2 2,3
0 60 S

200 0 None 0 60 0 NS
S
S
NS NS
S
3 30 3 4,6,7 10,20,25 30 30

4 90 1 5 60 40 20

5 100 250 1 0 6 50 0 0 55 0

6

None 0
0

7 150 0 None 0
5

TABLE 4: DATA FOR SUBJECT CODE FOR TIME = 60

Processor List of Start time Completion Processor
ID Scheduled for time for Availability
tasks scheduled tasks on scheduled task on real Time
(Pid) (LST) real time time scale
scale
(Ts) (Tc) (PAT)
1 1 0 100 60 40 0
h? H 3 3D

3 4 40 130 70
2 2 60 260 200
4 7 55 205 45
TABLE 5: PROCESSOR STATUS SHEET AT TIME = 400

6

Task ID
(Tid)
3 4
6
7

Task
execution
time
(Tx)
100
200
30
90
100
250
150

Number of
dependent
tasks
(NDT)

List of
Dependent
Tasks
(LDT)
2,3
None
4,6,7
None
None

Wait time
for
releasing
tasks
(Tw)
60,30
10,20,25
60
50

Start time
(relative to
individual
processor)
(Ts)
0
60 30 40
100
150
55

Elapsed time
for
corresponding
processor
(Te)
400 340 370 360 300 250
345

Task
Status
Flag
(SF)
S
NS S S
NS
NS
S

TABLE 6: DATA FOR SUBJECT CODE FOR TIME = 400

Processor List of Start time Completion Processor
ID Scheduled for time for Availability
Tasks scheduled tasks on scheduled task on real Time
(Pid) (LST) real time time scale
scale (Tc) (PAT)
1 2 (TS)

0 30,60 100 0

60, 260 0
3 4,6 40, 150 130,400 0 0
4 5 100 200

5 7 55 205 0
TABLE 7: PROCESSOR STATUS SHEET AT TIME = 400

7

FIG. 1: GRAPHICAL REPRESENTATION OF SCHEDULING OF TASKS IN AN ENVIRONMENT COMPRISING MULTIPLE PROCESSING ELEMENTS
ADVANTAGES OF THE PRESENT INVENTION
1) Tasks not synonymous to functions - thus, task is smallest unit program element that may be considered for scheduling.
2) Determines optimal number of resources required to achieve a practical overall task completion time
3) Adaptable to non computer applications
Submitted on this 28 Day of November 2008

8