US5961599A — Apparatus and method for computing the processing…

Claim 1

Independent Claim 129 words

Method for designing a system having resources enabling the concurrent execution of one or more adaptive applications, each of said adaptive applications consisting of a set of executable tasks sharing said system resources, said set of executable tasks having execution times depending on a particular adaptation level, said method comprising the steps of: a) mapping components of each said adaptive application to system resources; b) computing performance measures based upon a particular adaptation process, said performance measures including a measure of the resource contention at resource R; c) comparing resource contention at each particular resource with a predetermined threshold; and, d) if said resource contention at a particular resource is less than said predetermined threshold, then removing a most idle resource from said mapping and returning to step a).

Claim 2

Dependent Claim 129 words

Method for designing a system having resources enabling the concurrent execution of one or more adaptive applications, each of said adaptive applications consisting of a set of executable tasks sharing said system resources, said set of executable tasks having execution times depending on a particular adaptation level, said method comprising the steps of: a) mapping components of each said adaptive application to system resources; b) computing performance measures based upon a particular adaptation process, said performance measures including a measure of the resource contention at resource R; c) comparing resource contention at each particular resource with a predetermined threshold; and, d) if said resource contention at a particular resource is less than said predetermined threshold, then removing a most idle resource from said mapping and returning to step a).

Claim 3

Dependent Claim 27 words

Method for designing a system according to claim 1, wherein said step of computing performance measures includes the step of computing a processing delay of each application.

Claim 4

Dependent Claim 142 words

Method for designing a system according to claim 1, wherein the step of computing a processing delay of each application includes the steps of: a) modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level; b) modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution; c) modeling a system-wide computation by a state process, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process; d) calculating a stationary distribution π M from said stochastic state process; and, e) from said stationary distribution, calculating the processing delay of said adaptive applications.

Claim 5

Dependent Claim 60 words

Method for designing a system according to claim 3, wherein said step of modelling an adaptation process for each adaptive application includes the step of approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ m representing a long-term fraction of time spent by said application in an adaptation level m.

Claim 6

Dependent Claim 46 words

Method for designing a system according to claim 4, further including the step of modelling the computation offered by an application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

Claim 7

Dependent Claim 231 words

Method for designing a system according to claim 5, wherein system-wide state change occurs at specific time instances, each said time instants defined as a state transition time A n , said step of modelling said state process includes the step of generating a joint sequence (Y, Z,U) enabling reproduction of an evolution of said state process where Y is a vector sequence equal to {Y n , n=0, 1, . . . }, where Y n ,=(I, w I ), where I is a set of nodes ready and waiting at transition time A n - ,w I is the delay incurred by these nodes, and A n - denotes the time just prior to an n th transition time; Z is a vector sequence equal to {Z n , n=0, 1, . . . }, where Z n =(J, r J ) where J is a set of nodes that are running at transition time A n , r J is the remaining execution time of these nodes; and U is a vector sequence equal to {U n , n=0, 1, . . . }, where U n =(App, m App , t App ) where App is the application, m App is the adaptation application of application at instant A n - , and t App is the elapsed time of application at time A n - .

Claim 8

Dependent Claim 60 words

Method for designing a system according to claim 6, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k,l,c), said step d) of calculating a stationary distribution further including the step of computing a transition probability function defined by: ##EQU11## where (i,j,a), (k,l,c)εS, where S is the state space of state process X.

Claim 9

Dependent Claim 57 words

Method for designing a system according to claim 7, wherein said stationary distribution represents the probability that (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π M further including the step of solving a set of linear equations ##EQU12##

Claim 10

Dependent Claim 40 words

Method for designing a system according to claim 8, further including the step of calculating an unconditioned stationary distribution π regardless of adaptation level m, said step of calculating π including the step of solving a set of linear equations:

Claim 11

Dependent Claim 88 words

Method for designing a system according to claim 9, further including the step of calculating an average nodal wait time W b representing a mean time a said node "b" has to wait before it can run on the resource it is mapped to, said calculating step including the steps of solving an equation where r b is equal to a value of node b's remaining execution time and is equal to its execution time t b and w b ija represents node b's wait at state (i,j,a).

Claim 12

Dependent Claim 55 words

Method for designing a system according to claim 10, further including the step of calculating an average resource wait time W R representing said measure of the resource contention at resource R, said calculating step including the steps of solving an equation ##EQU13## where W b represents the average nodal wait time for node b.

Claim 13

Dependent Claim 170 words

Method for computing the processing delay of a terminal running a system of one or more adaptive applications, each adaptive application consisting of a set of executable tasks sharing system resources, said set of execution tasks having execution times depending on a particular adaptation level, said method comprising the steps of: a) modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level; b) modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution; c) modeling a system-wide computation by a state process X, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process; d) calculating a stationary distribution π M from said stochastic state process; and, e) from said stationary distribution, calculating the processing delay of said adaptive applications.

Claim 14

Dependent Claim 170 words

Method for computing the processing delay of a terminal running a system of one or more adaptive applications, each adaptive application consisting of a set of executable tasks sharing system resources, said set of execution tasks having execution times depending on a particular adaptation level, said method comprising the steps of: a) modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level; b) modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution; c) modeling a system-wide computation by a state process X, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process; d) calculating a stationary distribution π M from said stochastic state process; and, e) from said stationary distribution, calculating the processing delay of said adaptive applications.

Claim 15

Dependent Claim 19 words

A method according to claim 12, wherein said processing delay is calculated for a particular combination of adaptation levels.

Claim 16

Dependent Claim 19 words

A method according to claim 12, wherein said processing delay is calculated regardless of a combination of adaptation levels.

Claim 17

Dependent Claim 57 words

A method according to claim 12, wherein said step of modelling an adaptation process for each adaptive application includes the step of approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ m representing a long-term fraction of time spent by said application in an adaptation level m.

Claim 18

Dependent Claim 43 words

A method according to claim 15, further including the step of modelling the computation offered by an application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

Claim 19

Dependent Claim 229 words

A method according to claim 16, wherein system-wide state changes in a computation occur at specific time instances, each said time instants defined as a state transition time A n , said step of modelling said state process includes the step of generating a joint sequence (Y, Z,U) enabling reproduction of an evolution of said state process X where Y is a vector sequence equal to {Y n ,n=0, 1, . . . }, where Y n ,=(I, w I ), where I is a set of nodes ready and waiting at transition time A n - , w I is the delay incurred by these nodes, and A n - denotes the time just prior to an n th transition time; Z is a vector sequence equal to {Z n , n=0, 1, . . . }, where Z n =(J, r J ) where J is a set of nodes that are running at transition time A n ,r J is the remaining execution time of these nodes; and U is a vector sequence equal to {U n ,n=0, 1, . . . }, where U n =(App,m App , t App ) where App is the application, m App is the adaptation application of application at instant A n - , and t App is the elapsed time of application at time A n - .

Claim 20

Dependent Claim 57 words

A method according to claim 17, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k, l,c), said step d) of calculating a stationary distribution further including the step of computing a transition probability function defined by: ##EQU14## where (i,j,a), (k,l,c) εS, where S is the state space of X.

Claim 21

Dependent Claim 54 words

A method according to claim 18, wherein said stationary distribution represents the probability that (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π M further including the step of solving a set of linear equations ##EQU15##20.

Claim 22

Dependent Claim 37 words

A method according to claim 18, further including the step of calculating an unconditioned stationary distribution π regardless of adaptation level m, said step of calculating π including the step of solving a set of linear equations:

Claim 23

Dependent Claim 122 words

An application manager for optimizing system resources of a terminal in an interconnected network, said terminal having one or more concurrently running adaptive applications, each adaptive application consisting of a set of executable tasks sharing said system resources, said set of execution tasks having execution times depending on a particular adaptation level, said application manager comprising: means for receiving feedback information from said network, said feedback indicating network performance; means for computing a processing delay distribution for said terminal, said processing delay distribution based upon any combination of adaptation levels; and, means for changing an adaptation level for a particular adaptation application in accordance with said feedback information and said processing delay distribution computed for said terminal, whereby system resources are optimized.

Claim 24

Dependent Claim 122 words

An application manager for optimizing system resources of a terminal in an interconnected network, said terminal having one or more concurrently running adaptive applications, each adaptive application consisting of a set of executable tasks sharing said system resources, said set of execution tasks having execution times depending on a particular adaptation level, said application manager comprising: means for receiving feedback information from said network, said feedback indicating network performance; means for computing a processing delay distribution for said terminal, said processing delay distribution based upon any combination of adaptation levels; and, means for changing an adaptation level for a particular adaptation application in accordance with said feedback information and said processing delay distribution computed for said terminal, whereby system resources are optimized.

Claim 25

Dependent Claim 41 words

An application manager as claimed in claim 1, further including means for comparing a processing delay computed for a first adaptive application against a predetermined threshold and determining feasibility of said change in said adaptation level of a second adaptive application.

Claim 26

Dependent Claim 41 words

An application manager as claimed in claim 22, wherein said means for computing a processing delay distribution for said terminal, further including means for determining a combination of adaptation level changes whereby excess delay probabilities for all adaptive applications are feasible.

Claim 27

Dependent Claim 146 words

An application manager as claimed in claim 21, wherein said step of computing the processing delay for said terminal comprises: means for modelling the adaptation of each adaptive application as an adaptation process having a steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level; means for modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution; means for modelling a system-wide computation by a state process X, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process; and, means for calculating a stationary distribution π M from said stochastic state process, said processing delay for said terminal being calculated from said stationary distribution π M .

Claim 28

Dependent Claim 20 words

An application manager according to claim 24, wherein said processing delay is calculated for a particular combination of adaptation levels.

Claim 29

Dependent Claim 58 words

An application manager according to claim 25, wherein said means for modelling an adaptation process for each adaptive application further includes means for approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ m representing a long-term fraction of time spent by said application in an adaptation level m.

Claim 30

Dependent Claim 44 words

An application manager according to claim 26, further including means for modelling the computation offered by an adaptation application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

Claim 31

Dependent Claim 232 words

An application manager according to claim 27, wherein said means for receiving feedback information from said network occurs at specific time instants, each said time instants defined as a state transition time A n , said means for modelling the system-wide computation further including means for generating a joint sequence (Y,Z,U) enabling reproduction of an evolution of said state process where Y is a vector sequence equal to {Y n ,n=0, 1, . . . }, where Y n ,=(I,w I ), where I is a set of nodes ready and waiting at transition time A n - , w I is the delay incurred by these nodes, and A n - denotes the time just prior to an n th transition time; Z is a vector sequence equal to {Z n ,n=0, 1, . . . }, where Z n =(J, r J ) where J is a set of nodes that are running at transition time A n , r J is the remaining execution time of these nodes; and U is a vector sequence equal to {U n , n=0, 1, . . . }, where U n =(App, m App , t App ) where App is the application, m App is the adaptation application of application at instant A n - , and t App is the elapsed time of application at time A n - .

Claim 32

Dependent Claim 55 words

An application manager according to claim 28, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k,l,c), said means for calculating a stationary distribution further including means for computing a transition probability function defined by: ##EQU16## where(i,j,a),(k,l,c) εS, where S is the state space of state process X.

Claim 33

Dependent Claim 57 words

An application manager according to claim 29, wherein said stationary distribution represents the probability that said joint process (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π M further including means for solving a set of linear equations ##EQU17##

Claim 34

Dependent Claim 31 words

An application manager according to claim 30, further including means for calculating an unconditioned stationary distribution π regardless of adaptation level m, said calculating means solving a set of linear equations:

Claim 35

Dependent Claim 18 words

An application manager according to claim 23, wherein said adaptive application includes one of video and audio applications.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-10-04	2003-04-05	2003-10-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-10-04	2007-04-05	2007-10-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-10-04	2011-04-05	2011-10-05	$7700.00	Window Closed / Lapsed

Apparatus and method for computing the processing delay of adaptive applications network terminals and applications thereof

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag