Abstract:
The invention provides a method and system for handling reflex interrupts using orthogonal device vector function (ODVF). The method includes receiving parameters associated with interrupt devices and assigning a Walsh function to each interrupt device. Further, the method includes generating an interrupt prediction matrix based on the received parameters and the assigned Walsh function and predicting next occurrence of interrupt associated with the interrupt devices using the interrupt prediction matrix.
FIG. 16
Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence
FIELD OF INVENTION
[001] The present invention relates to handling interrupts in a
mobile communication system, and more particularly to a mechanism for
predicting, managing, and scheduling reflex interrupts using orthogonal
device vector function (ODVF).
5
BACKGROUND OF INVENTION
[002] Interrupts can signal a computing system of an event to be
serviced by execution of an interrupt handler, which may also be known as
an interrupt service routine (ISR). Such a signal event can be referred to as
10 an interrupt request (IRQ). A processor can undergo a context switch to
transition from its current task to execute the interrupt handler associated
with a received interrupt.
[003] Conventional methods and systems proposed to mange
interrupts can include polling, interrupt handling, bus arbitration, and the
15 like. The polling allows faster response to devices for virtually sharing
information with processor(s). At a given time, the polling method allows
only one device to share the data thereby maintaining the processor to be in
waiting mode till the device shares the data. Further, the interrupt handling
method allow the processor to run in asynchronous mode, which enables
20 the processor to perform other task/process’s till the data is
collected/received by the device and is ready to share. The handler may
save additional context depending on the details of respective hardware and
software design, which may maximize the amount of time spent in handling
the interrupt.
25 [004] Though the conventional systems and methods are effective to
a degree in handling the interrupts but, include both advantages and
disadvantages in terms of processor utilization, time, cost, memory
management, registers used, interrupt management, interrupt, interrupt
3/55
scheduling, interrupt analysis, context switching, synchronization,
reliability, and security.
OBJECT OF INVENTION
[005] The principal object of the embodiments herein is to provide 5 a
method and system for handling reflex interrupts using orthogonal device
vector function (ODVF).
[006] Another object of the invention is to provide a method and
system for predicting next occurrence of interrupts using Walsh function.
10 [007] Another object of the invention is to provide a method and
system for efficiently scheduling interrupt using ODVF bus mechanism.
[008] Another object of the invention is to provide a method and
system for analyzing interrupt patterns to predict next occurrence of
interrupt(s).
15 [009] Another object of the invention is to provide a method and
system for generating and updating an interrupt prediction matrix for
efficiently managing and scheduling interrupts associated with devices.
[0010] Another object of the invention is to provide a mechanism to
reduce number of context switch using orthogonal device vector function
20 (ODVF).
SUMMARY
[0011] Accordingly the invention provides a method for handling
reflex interrupts using orthogonal device vector function (ODVF). The
25 method includes receiving parameters associated with interrupt devices and
assigning a Walsh function to each interrupt device. Further, the method
includes generating an interrupt prediction matrix based on the received
parameters and the assigned Walsh function and predicting next occurrence
4/55
of interrupt associated with the interrupt devices using the interrupt
prediction matrix.
[0012] In an embodiment, the parameters associated with the
interrupt devices includes interrupt device identifier, status data, Walsh
function data, interrupt pattern, data signal, timing signal, feedback data5 ,
and the like. Furthermore, the method includes storing the received
parameters and analyzing the parameters associated with the interrupt
devices. Furthermore, the method includes generating the interrupt
prediction matrix, including data related to the Walsh function associated
10 with the interrupt devices and timing signal, based on the analysis of the
parameters. In an embodiment, the timing signal includes the interrupt start
time, the interrupt end time, and the like.
[0013] Furthermore, the method includes frequently monitoring the
parameters associated with the interrupt device, updating the interrupt
15 prediction matrix based on the monitoring results and scheduling the
interrupt associated with the interrupt device based on the newly updated
interrupt prediction matrix. Furthermore, the method includes generating
the Walsh function for the interrupt device and maintaining a list of
generated Walsh function including the Walsh function assigned to the
20 interrupt device and Walsh function released from the interrupt device.
Furthermore, the method includes regenerating the Walsh function for the
interrupt device and reassigning the Walsh function for the interrupt device
based on the list of Walsh functions.
[0014] Accordingly the invention provides a system for handling
25 reflex interrupts using orthogonal device vector function (ODVF). The
system includes an ODVF buffer module configured to receive parameters
associated with the interrupt device and a Walsh function module
configured to assign the Walsh function for the interrupt device. Further,
the system includes an ODVF controller module configured to generate an
5/55
interrupt prediction matrix based on the parameters and the Walsh function,
and predict the interrupt associated with the interrupt device using the
interrupt prediction matrix.
[0015] Further, the ODVF buffer module is configured to store the
received parameters associated with the interrupt device. The ODV5 F
controller module is further configured to analyze the parameters associated
with the interrupt device and generate the interrupt prediction matrix based
on the analysis of the parameters. In an embodiment, the interrupt
prediction matrix includes data related to the Walsh function data
10 associated with the interrupt devices and timing signal including the
interrupt start time, the interrupt end time, and the like.
[0016] Furthermore, the ODVF controller module is configured to
frequently monitor the parameters associated with the interrupt device,
update the interrupt prediction matrix based on the monitoring result, and
15 schedule the interrupt associated with the interrupt device based on the
newly updated interrupt prediction matrix.
[0017] Furthermore, the ODVF controller module is configured to
maintain a list of Walsh function generated including the Walsh function
assigned to the interrupt device, Walsh function released from the interrupt
20 device, and the like. Furthermore, the Walsh function module is configured
to regenerate the Walsh function for the interrupt device and reassign the
Walsh function to the interrupt device based on the list of Walsh function.
[0018] These and other aspects of the embodiments herein will be
better appreciated and understood when considered in conjunction with the
25 following description and the accompanying drawings. It should be
understood, however, that the following descriptions, while indicating
preferred embodiments and numerous specific details thereof, are given by
way of illustration and not of limitation. Many changes and modifications
may be made within the scope of the embodiments herein without departing
6/55
from the spirit thereof, and the embodiments herein include all such
modifications.
BRIEF DESCRIPTION OF FIGURES
[0019] This invention is illustrated in the accompanying drawings,
throughout which like reference letters indicate corresponding parts in the
various figures. The embodiments herein will be better understood from th5 e
following description with reference to the drawings, in which:
[0020] FIG. 1 illustrates a system including a processor, according
to embodiments as disclosed herein;
[0021] FIG. 2 illustrates generally, among other things, a layered
10 architecture of the system as described in the FIG.1, according to
embodiments as disclosed herein;
[0022] FIG. 3 is a block diagram illustrating generally, among other
things, various modules present in orthogonal device vector function
(ODVF) bus controller layer as described in the FIG. 2, according to
15 embodiments as disclosed herein;
[0023] FIG. 4 illustrates generally, an exemplary ODVF interrupt
data format, according to embodiments as disclosed herein;
[0024] FIG. 5 is a schematic diagram illustrating operations
performed by ODVF buffer module as described in the FIG. 3, according to
20 embodiments as disclosed herein;
[0025] FIG. 6 is a schematic diagram illustrating operations
performed by Walsh function module as described in the FIG. 3, according
to embodiments as disclosed herein;
[0026] FIG. 7 shows exemplary levels of Walsh functions generated
25 for an interrupt, according to embodiments as disclosed herein;
7/55
[0027] FIG. 8 is a schematic diagram illustrating operations
performed by interrupt prediction matrix as described in the FIG. 3,
according to embodiments as disclosed herein;
[0028] FIG. 9 shows an exemplary interrupt prediction matrix as
described in the FIG. 8, according to embodiments as disclosed herein5 ;
[0029] FIG. 10 is a diagram illustrating operations performed by
ODVF INT module to schedule interrupts as described in the FIG. 3,
according to embodiments as disclosed herein;
[0030] FIG. 11A is a diagram illustrating an exemplary interrupt
10 task scheduling logic, according to embodiments as disclosed herein;
[0031] FIG. 11B is a timing diagram for the interrupt task
scheduling logic described in the FIG. 11A, according to embodiments as
disclosed herein;
[0032] FIG. 12A is a diagram illustrating an exemplary preemptive
15 interrupt task scheduling logic, according to embodiments as disclosed
herein;
[0033] FIG. 12B is a preemptive timing diagram for the interrupt
task scheduling logic described in the FIG. 12A, according to embodiments
as disclosed herein;
20 [0034] FIG. 13 is a diagram illustrating division of ODVF,
according to embodiments as disclosed herein;
[0035] FIG. 14 is a graph showing an exemplary time scale of the
interrupt handling system, according to embodiments as disclosed herein;
[0036] FIG. 15 is a schematic diagram illustrating various
25 operations performed by the system, according to embodiments as
disclosed herein;
[0037] FIG. 16 is a flow diagram illustrating a method for handling
reflex interrupts using ODVF, according to embodiments as disclosed
herein; and
8/55
[0038] FIG. 17 depicts a computing environment implementing the
application, in accordance with various embodiments of the present
invention.
9/55
DETAILED DESCRIPTION OF INVENTION
[0039] The embodiments herein and the various features and
advantageous details thereof are explained more fully with reference to the
non-limiting embodiments that are illustrated in the accompanying
drawings and detailed in the following description. Descriptions of well5 -
known components and processing techniques are omitted so as to not
unnecessarily obscure the embodiments herein. The examples used herein
are intended merely to facilitate an understanding of ways in which the
embodiments herein can be practiced and to further enable those skilled in
10 the art to practice the embodiments herein. Accordingly, the examples
should not be construed as limiting the scope of the embodiments herein.
[0040] The embodiments herein achieve a method and system for
handling reflex interrupts using orthogonal device vector function (ODVF).
One or more interrupt devices can generate interrupts signals for a task or
15 event to be serviced by execution of an interrupt handler (or interrupt
service routine (ISR)). The method includes receiving parameters
associated with the interrupt devices in a communication system. The
parameters described herein can include interrupt device identifier, status
data, Walsh function data, interrupt pattern, data signal, timing signal, and
20 the like. The various parameters associated with the interrupt device are
analyzed and an interrupt prediction matrix is generated to predict next
occurrence of interrupts. A Walsh function is assigned to each interrupt
device to uniquely identify the interrupt devices in the communication
system and predict the next occurrence of the interrupt using the Walsh
25 function. In accordance to the interrupt prediction matrix, at predicated
time respective ISR is scheduled to process the interrupts.
[0041] In an embodiment, the orthogonal device vector function
(ODVF) described herein can be a periodic logical algorithm, which can be
mathematically represented by an orthogonal function under time bounded
10/55
range. For example, universal asynchronous receiver/transmitter (UART)
device along with software drivers can be represented as one ODVF.
Mathematically, the UART device vector can be orthogonal with other
device vector function like liquid crystals display (LCD). The LCD device
vector function can periodically generate completion of frame interrupt an5 d
the next interrupt predication can be LCD date received bit rate. The UART
and LCD can be represented by different ODVF. Each of the ODVF
represents the complete mathematical and algorithm process of production
and consumption of information, which can be either input or output to
10 real-time system.
[0042] The method and system disclosed herein is simple, dynamic,
robust, and reliable to handle, analyze, predict, manage, and schedule
interrupts using orthogonal device vector function. The system and method
can be used to enhance processor response time for the interrupt devices
15 and efficiently utilize the processor for handling interrupts at a reasonable
system cost and time. Context switch is an important feature of
communications system (e.g., instruction-level parallelism,
multiprogramming paradigm, and the like). The present invention can be
used to perform context switch with lesser payload for saving/restring
20 registers, depending on task time slice and interrupt prediction. Further, the
system and method can be used to enable more instruction level parallelism
and optimizes the real-time performance of the system.
[0043] Referring now to the drawings, and more particularly to
FIGS. 1 through 17, where similar reference characters denote
25 corresponding features consistently throughout the figures, there are shown
preferred embodiments.
[0044] FIG. 1 illustrates a system 100 including a processor 102,
according to embodiments as disclosed herein. The processor 102 may be
coupled to a variety of interrupt sources 1041-N (hereafter referred as
11/55
interrupt source(s) 104) over a communication network 106. In an
embodiment, the network 106 described herein can represent a number of
distinct computer networks or communication mediums. For example, the
network 106 may include, but not limited to, wireless network, wire-line
network, public network such as the Internet, local area network, wide are5 a
network, personal area network, private network, cellular network, global
system for mobile communication network (GSM), combination thereof, or
any other network. The system 100 can include a variety of communication
buses for exchanging information with electronic devices or subsystems
10 (e.g., sensors or other actuators). The processor 102 can integrate the
resources of multiple types of hardware and/or software systems. In an
embodiment, the processor 102 described herein can be a central processing
unit (CPU), microprocessor, microcontroller, a combination thereof or any
other processor capable of processing instructions to handle the interrupts
15 received from the various interrupts sources.
[0045] In an embodiment, the processor 102 can be configured to
receive a variety of interrupts (1-N) from the interrupt sources(s) 104. The
interrupt sources 104 described herein can include, for example, but not
limited to, software applications, mobile devices, web services, electronic
20 devices, computers, or other interrupt sources. In an embodiment, the
interrupt(s) generated by the interrupt sources 104 can be reflexive in
nature. Unlike general interrupts, the reflex interrupts can be defined as the
interrupts generated without any conscious action/response to/from the
system. For example, the interrupts may be performed without any
25 conscious action/response to/from the system 100 or the interrupts may be
performed irrespective of hardware and software design of the system 100.
In an embodiment, the reflex interrupt can be generated based on correct
mathematically representation (Walsh function) of interrupt pattern
generated by the interrupt source. When the mathematically representation
12/55
is correct then each reflex interrupt can be executed, which can be served
better than the general interrupts. In an embodiment, when the reflex
interrupt miss occurs (such as when the system predicts an interrupt where
the interrupt source does not generate the data) then the system can be
reconfigured to predict again. Each interrupt sent or received from th5 e
interrupt source 104 over the network 106 can include particular content
(e.g., a task, message, instruction, data, or the like) and additional
information such as for example, information identifying the source of the
interrupt, interrupt type, priority information, activity status of the device
10 generating the interrupt (e.g., busy or idle), and the like.
[0046] In an embodiment, different interrupt sources 104 can
generate different types of interrupt patterns. The processor 102 can be
configured to detect interrupts generated by the interrupt sources 104.
Further, the processor 102 can be configured to handle the interrupts based
15 on the priorities of the interrupts and can predict next occurrence of
interrupts based on the trend of interrupts for efficiently managing the
processor time thereby significantly increasing overall system performance
at a reasonable system cost. Further, the system can be used on any
computer, device, processor, micro-controller, a combination thereof, or as
20 a software component application, driver, and the like. The detailed
overview of the system 100 is described in conjunction with FIGS. 2
through 16.
[0047] FIG. 2 illustrates generally, among other things, a layered
architecture 200 of the system 100 as described in the FIG.1, according to
25 embodiments as disclosed herein. In an embodiment, the architecture 200
includes three layers namely, interrupt sources layer 202, orthogonal device
vector function (ODVF) bus controller layer 204, and processing layer 204
respectively.
13/55
[0048] In an embodiment, the interrupt sources layer 202 described
herein can include interrupts data generated from various interrupt sources
104 (such as the orthogonal devices when respective input data is
available). The system 100 can be configured to transfer the interrupt
information to the ODVF bus controller layer 204. The present inventio5 n
uses the ODVF function to enhance the system performance, time, and
usage. The orthogonal vectors originating from Walsh function can be used
to efficiently manage, predict, analyze, schedule, and handle the interrupts
throughout the system100. In an embodiment, the layer 204 includes a
10 ODVF controller module 206 configured to analyze the interrupt
information received from the interrupt sources layer 202 and predict the
next occurrence of interrupts using a interrupt predict matrix and Walsh
function. The ODVF controller 206 configured to predict and schedule
respective interrupt in the system 100, such as to efficiently utilize the
15 system time at a reasonable system cost. Further, the various components or
modules present in the ODVF bus controller layer 204 of the system 100
are described in conjunction with the FIG.3.
[0049] In an embodiment, the processing layer 206 can include a
processor module 208 to process the interrupts throughout the system 100.
20 The processor module 208 can be configured to process the information
about the interrupts (for example, ready or queued) predicted by the ODFV
bus controller layer 204. The processor module 208 can be configured to
include or be coupled to a scheduler module 210 (also referred as
dispatcher module) for scheduling the respective predicted interrupts in
25 accordance to the interrupt prediction matrix. Further, the various
operations performed by the system 100 to analyze, predict, manage,
handle, and schedule various interrupts are described in conjunction with
the FIGS. 3 through 16.
14/55
[0050] FIG. 3 is a block diagram illustrating generally, among other
things, various modules 300 present in the ODVF bus controller layer 204
as described in the FIG. 2, according to embodiments as disclosed herein.
In an embodiment, the system 100 can include an ODVF buffer module
302, a Walsh function module 304, the ODVF controller module 206, an5 d
an ODVF bus arbitration module 306.
[0051] In an embodiment, the ODVF buffer module 302 described
herein can be configured to receive parameters associated with the interrupt
sources 104. In an embodiment, the parameters described herein can
10 include for example, but not limited to, interrupt device identifier, status
data, Walsh function data, interrupt pattern, data signal, timing signal, and
feedback data. Any change in these parameters can affect the performance
and reliability of the system 100. The system 100 can use the interrupt
device identifier to uniquely identify the device responsible for generating
15 the interrupt. The status of the device, such as active, passive, idle, sleep,
wait, hold, join, leave, or the like, can be used by the system 100 to
schedule the interrupts. The system 100 can be further configured to
analyze the interrupt patterns and predict the next occurrence of the
interrupt. Further, the operations performed by the ODVF buffer module
20 302 is described in conjunction with the FIG. 5.
[0052] In an embodiment, the Walsh function module 304 can be
configured to assign Walsh function (also referred as Walsh code) to each
interrupt source 104. The assigned Walsh function for the interrupt source
104 along with the interrupt source identifier can be stored in the ODVF
25 buffer module 302. The Walsh function module 304 can be configured to
generate Walsh function for each interrupt source 104 using a Walsh
function. The Walsh function described herein represent interrupt pattern of
interrupt source. In an embodiment, the Walsh function module 304 can be
configured to use the assigned Walsh codes and free codes data in real-time
15/55
to use the efficiently use the codes and enhance the performance of the
system 100. Further, various operations performed by the Walsh function
module 304 is desired in conjunction with the FIG. 6.
[0053] In an embodiment, the ODVF controller module 206 can be
configured to analyze the parameters associated with the interrupt source5 .
For example, the ODVF controller module 206 can be configured to
analyze the Walsh function, the interrupt device identifier (ID), interrupt
patterns, timing signal, and the like interrupt data/signal, to generate an
interrupt prediction matrix 308. The ODVF controller module 206 can be
10 configured to predict the next occurrence of the interrupt using the interrupt
prediction matrix 308 and the Walsh function. The various operations
performed by the ODVF controller module 206 to generate the interrupt
prediction matrix 308 are described in conjunction with the FIG. 8.
[0054] Further, the ODVF controller module 206 can be configured
15 to functions in two modes namely, Boot time and Kernel respectively. In an
embodiment, during boot time the ODVF controller module 206 can be
configured to work at default frequency. Input and output request to fetch
data, provide data, and device information can be processed
asynchronously, as soon as the ODVF Bus is free. As the Kernel is not
20 running and there is no context switching occurring, the ODVF controller
module 206 can work in default frequency and generate interrupt as the
data and/or device information is ready to transfer. In an embodiment,
ODVF controller module driver can be embedded in boot loader, which
entirely utilizes the ODVF controller module 206 as no other parallel
25 activity or process is performed. In an embodiment, the boot loader can
allow the ODVF controller module 206 to load and execute kernel binary,
digital signal processing (DSP) images, root file system, and the like into
random access memory (RAM). In an embodiment, all asynchronous
requests from the boot loader can be send by pull-up active signal to the
16/55
ODVF controller module 206 till next active high clock signal occurs. If the
clock reaches then the address latch can be fetched on multiplex address
and the data bus, which combines the address of device and address of
register (such as offset register) inside the device.
[0055] Furthermore, the ODVF controller module 206 can be can b5 e
configured to include an ODVF INT module 310 and an ODVF task
module 312 for scheduling the interrupts in accordance with the interrupt
prediction matrix 308. The ODVF INT module 310 can be configured to
schedule the respective interrupt using the interrupt prediction matrix 308
10 and the Walsh function. The various operations performed by the ODVF
INT module 310 to schedule the predicted interrupts are described in
conjunction with the FIGS. 10 and 11.
[0056] In an embodiment, the ODVF task module 312 can be
configured to allow the various interrupt sources 104 to follow real-time
15 task criteria for processing the tasks associated with the interrupts. The
ODVF task module 312 can be configured to calculate a Worst case
execution time (WCET) and average case execution time (ACET) for each
tasks associated with the interrupts. Further, the calculation of the WCET
and the ACET is described in conjunction with the FIG. 13.
20 [0057] In an embodiment, the ODVF bus arbitration module 306
can be configured to connect the interrupt devices served by the ODVF bus
at any given time. The ODVF controller module 206 can use the ODVF bus
arbitration module 306 to determine the interrupt to be handled by the
ODVF bus at a given time based on the interrupt priorities and interrupt
25 predication matrix 308. The ODVF bus arbitration module 306 can be
configured to enable an optimal way for sharing the data using the ODVF
bus in accordance to the interrupt predication matrix 308.
[0058] FIG. 4 illustrates generally, an exemplary ODVF interrupt
data format 400, according to embodiments as disclosed herein. The system
17/55
100 can receive the timing and other information from the ODVF controller
206 in a packet format. In an embodiment, the FIG. 4A shows the ODVF
interrupt data format 400 including three sections namely, header section
402, data section 404, and tail section 406 respectively.
[0059] In an embodiment, the header section 402 of the ODV5 F
interrupt data format 400 indicates the type of data included in the interrupt.
FIG. 4B shows the header section 402 including the data related to the
interrupts schedule for the processor, total interrupt sources, total processor
usage time, total time interval between interrupts, and time interval
10 allocated for interrupts.
[0060] In an embodiment, the data section 404 of the ODVF
interrupt data format 400 indicating the data related to the interrupt. FIG.
4C shows the data section 402 including the data related to the interrupts,
such as for example, but not limited to, interrupt source identifier, task start
15 time, task end time, data, and the like.
[0061] In an embodiment, FIG. 4D shows the tail section 406 of the
ODVF interrupt data format 400 indicating the data end information and
cyclic redundancy check (CRC) of the data related to the interrupt. The
CRC can be used to ensure that the schedule packet is received by the
20 processor module 208 before completion of the tasks associated with the
interrupts (If the packet is corrupted then the data packet can be discarded).
In an embodiment, the scheduler module 210 dispatches the next packet
before ending the previous allocated task to avoid waiting time of the
processor.
25 [0062] FIG. 5 is a schematic diagram 500 illustrating operations
performed by the ODVF buffer module 302 as described in the FIG. 3,
according to embodiments as disclosed herein. In an embodiment, the
ODVF buffer module 302, in communication with the ODVF controller
module 206, can be configured to receive parameters associated with the
18/55
interrupt sources 104. The parameters described herein can include for
example, but not limited to, interrupt device identifier, status data, Walsh
function data, interrupt pattern, data signal, timing signal, feedback data,
and the like. The ODVF controller module 206 can use the interrupt device
identifier to uniquely identify the interrupt sources. The status dat5 a
described herein can include for example, but not limited to, active,
passive, idle, sleep, wait, hold, join, leave, or the like. The ODVF controller
module 206 can use status information schedule the predicted interrupts
when the device status is active or send the device into queue state for
10 effectively utilizing the system time.
[0063] In an embodiment, the ODVF controller module 206 can use
the Walsh function to uniquely identify the interrupt devices which are
under ready, idle, sleep, wait, hold, join, leave, or the like states. The timing
signal described herein can include interrupt start time, interrupt end time,
15 time required by the processor to complete the interrupt, time interval
between the interrupts, and the like. The ODVF controller module 206
analyzes the timing signals, interrupt patterns, and the like to predict the
next occurrence of the interrupt. Further, the ODVF buffer module 302 can
be configured to store the parameters in order to use the information for
20 determining effective predictions of the interrupts.
[0064] FIG. 6 is a schematic diagram 600 illustrating operations
performed by the Walsh function module 304 as described in the FIG. 3,
according to embodiments as disclosed herein. In an embodiment, the
Walsh function module 304 can be configured to assign Walsh function to
25 each interrupt source 104. As shown in the FIG. 6, a Walsh function can be
generated for each interrupt source 104 to uniquely identify the sources of
interrupt. The ODVF controller module 206 can be configured to store a list
of assigned to the interrupt source(s) 104 and compares the Walsh functions
against the list. For example, if the assigned Walsh function matches with
19/55
the previously assigned Walsh function then the ODVF controller module
206 can be configured to generate a new Walsh function for the interrupt
source 104. Exemplary levels of Walsh functions generated for an interrupt
is described in conjunction with the FIG. 7.
[0065] Further, the ODVF controller module 206 can be configure5 d
to maintain a list of Walsh functions deassigned (or made free) by the
processor. For example, upon completing the interrupt task or leaving or
joining other interrupts, the processor can be configured to release the
Walsh function assigned to the interrupt source 104. The ODVF controller
10 module 206 can be configured to maintain a list of Walsh functions
released by the processor, such as to allow the Walsh function module 304
to assign the same Walsh function to other interrupt sources. The list of
assigned and released Walsh functions can be used by the Walsh function
module 304 to efficiently use the Walsh functions and manage the system
15 time and cost. The ODVF controller module 206 can be configured to free
or release the Walsh functions, which are not in use or the interrupts task is
completed or handled. In an embodiment, the assigned Walsh functions for
the interrupt source 104 along with the interrupt source identifiers can be
stored or saved in the ODVF buffer module 302.
20 [0066] FIG. 7 shows exemplary levels of Walsh functions 700
generated for an interrupt, according to embodiments as disclosed herein.
In an embodiment, upon receiving any interrupt signal, the Walsh function
module 304 can be configured to generate a Walsh for each interrupt source
104. The Walsh function module 304 can be configured to compare the
25 generated Walsh function with the list of Walsh functions used, assigned,
and released by the processor. If the generated Walsh function matches
with any Walsh function present in the list, then the Walsh function module
304 can be configured to regenerate another Walsh function for the
interrupt source 104. The FIG. 7 shows exemplary five levels of Walsh
20/55
function generated for an interrupt upon detecting a match with the Walsh
functions present in the list. For example, as shown in the FIG.7, the Walsh
function module 304 can be configured to generate a first level of Walsh
function for the interrupt source 104. If the generated Walsh function
matches with the Walsh functions present in the list then the Wals5 h
function module 304 can be configured to generate a second level of Walsh
function for the interrupt source 104. Further, If the second level generated
Walsh function matches with the Walsh functions present in the list then
the Walsh function module 304 can be configured to generate a third level
10 of Walsh function for the interrupt source 104. Furthermore, If the third
level generated Walsh function matches with the Walsh functions present
in the list then the Walsh function module 304 can be configured to
generate a fourth level of Walsh function for the interrupt source 104.
Similarly, If the fourth level generated Walsh function matches with the
15 previously used or with the Walsh functions present in the list then the
Walsh function module 304 can be configured to generate a fifth level of
Walsh function for the interrupt source 104.
[0067] In an embodiment, the Walsh function module 304 can be
configured to assign any Walsh function which is free, unused, or released
20 by the processor. The ODVF controller module 206 can be configured to
analyze the Walsh functions, interrupt source identifiers, interrupt source
status data, and the like data, such as to allow Walsh function module 304
to efficiently assign Walsh functions to the interrupt sources. An example
analysis table (or matrix) managed by the ODVF controller module 206 is
25 shown below:
Interrupt Sources
(1-N)
Status
(Active)
Status
(Queue)
interrupt
sources
Status
(Inactive)
Status
(Others)
21/55
interrupt sources
1
Walsh
function
1
interrupt sources
2
Walsh
function
2
interrupt sources
3
Walsh
function 3
interrupt sources
4
Walsh
function
4
interrupt sources
5
Walsh
function 5
interrupt sources
N
Walsh
function
N
[0068] The Walsh function module 304 can be configured to use the
analysis data to efficiently generate and assign Walsh functions to the
interrupt sources. Further, in an embodiment, the Walsh functions can be
assigned by the system user or administrator.
[0069] The levels of Walsh functions and the analysis data show5 n
with respect to the FIG. 7 is only for illustrative. Further, in real-time any
number of levels of Walsh function can be generated and the analysis data
can be presented in any other form, without departing from the scope of the
invention.
10 [0070] FIG. 8 is a schematic diagram 800 illustrating operations
performed by the interrupt prediction matrix 308 as described in the FIG. 3,
according to embodiments as disclosed herein. In an embodiment, the
ODVF controller module 206 can be configured to analyze the Walsh
22/55
function, the interrupt device identifier, interrupt patterns, status data,
timing signal, and the like, to generate an interrupt prediction matrix 308.
The ODVF controller module 206 can be configured to use the analysis
information (such as described in the FIG. 7) to create the interrupt
prediction matrix 308. The ODVF controller module 206 can be configure5 d
to map the interrupt analysis data to create the interrupt prediction matrix
308. The interrupt prediction matrix 308 described herein can include for
example, but not limited to, the data/information related to the interrupt
sources Identifiers and associated Walsh functions assigned by the Walsh
10 function module 304, time taken by the interrupt tasks, and the gap time (or
time interval) between the interrupts. The interrupt prediction matrix 308
can be used by the ODVF controller module 206 to predict next occurrence
of the interrupts and efficiently manage the system performance, time, and
cost. Further, the ODVF controller module 206 can be configured to
15 frequently update the interrupt prediction matrix 308 based on the status of
interrupts and feedback (information about the interrupts in-process and
completed) from the processor.
[0071] FIG. 9 shows an exemplary interrupt prediction matrix 900
as described in the FIG. 8, according to embodiments as disclosed herein.
20 As shown in the FIG. 9, the exemplary interrupt prediction matrix 308 can
be created using the interrupt data analyzed by the ODVF controller
module 206. The matrix 900 shows the information related to interrupt data
available time, time required by the processor to process the interrupt, time
interval between the time interval (or gap time) between the interrupts, and
25 the like. The ODVF controller module 206 can be configured to use the
interrupt prediction matrix 308 to predict the next occurrence of interrupt
throughout the system 100. Further, the ODVF controller module 206 can
be configured to schedule other interrupts during the time interval (or the
gap time) between the interrupts to efficiently utilize the processor time and
23/55
enhance the performance of the system 100. An interrupt exemplary
interrupt prediction and schedule logic are described in conjunction with
the FIGS. 10 through 12.
[0072] FIG. 10 is a diagram 1000 illustrating operations performed
by the ODVF INT module 310 to schedule the interrupts as described in th5 e
FIG. 3, according to embodiments as disclosed herein. In an embodiment,
the ODVF INT module 310 can be configured to analyze the interrupt
prediction matrix 308 to schedule the interrupts throughout the system 100.
The ODVF INT module 310 can be configured to schedule the respective
10 interrupt using the interrupt prediction matrix 308 and the Walsh function.
The ODVF INT module 310 can be configured to determine the interrupt
timing signal and the gap (time interval) between the interrupts. An
exemplary information/data determined by the ODVF INT module 310
using the interrupt prediction matrix 308 are shown below:
Task
Start
Task
End
Gap
(Time
interval)
Task
Start
Task
End
Gap
(Time
interval)
Interrupt source 1
Walsh function 1
Interrupt source 2
Walsh function 2
Interrupt source 3
Walsh function 3
Interrupt source 4
Walsh function 4
Interrupt source 5
Walsh function 5
Interrupt source N
Walsh function N
24/55
[0073] In an embodiment, the interrupt predication logic is formed
as closed loop control system with the feedback from the processor module
208. The Walsh functions are used to formulate the interrupt pattern of
input generating device (which can be represented by the ODVF on th5 e
software side). In an example, when the ODVF controller module 206
predicts the interrupt correctly then there can be no change in the respective
ODVF.INT time value of the interrupt prediction matrix 308. In an
example, when the ODVF controller module 206 may not predicts the
10 interrupt correctly then the interrupt miss happens. The ODVF controller
module 206 can be configured to change the time (for prediction of
interrupt) at which the interrupt schedules for the respective ODVF.INT. In
an embodiment, the increase or decrease of time from the previous
occurrence of interrupt can be calculated. The calculated time can be then
15 compared with a threshold value (other bit rate value) in the interrupt
prediction matrix 308. If the calculated time value can be proportional to
the next or previous value in the interrupt prediction matrix 308 with
respect to the interrupt source then ODVF controller module 206
determines that the interrupt source is working in next or pervious bit rate
20 configuration. Further, the new value can be used to predicate the interrupt
to old performance.
[0074] Further, the ODVF INT module 310 can be configured to
schedule the interrupts using the interrupt prediction matrix information.
The ODVF INT module 310 can be configured to determine the gap (or the
25 time interval) between the interrupts and schedule other interrupts during
the gaps, such as to efficiently manage the processor time and performance.
As shown in the FIG. 10, the ODVF INT module 310 can schedule the
interrupt source 1-N to the processor based on the analysis of the interrupt
prediction matrix data. The ODVF INT module 310 can be configured to
25/55
use the interrupt device status information, the gap data between the
interrupts, timing signal of the interrupts, interrupt data availability, and the
like data to schedule and reschedule the predicated interrupts. In an
embodiment, the ODVF INT module 310 can be configured to use an
interrupt scheduling logic to schedule the interrupts for the processor. A5 n
exemplary interrupt scheduling logic and associated timing signal is
described in conjunction with the FIG. 11.
[0075] FIG. 11A is a diagram 1100 illustrating an exemplary
interrupt task scheduling logic for scheduling the interrupts using the
10 interrupt prediction matrix, according to embodiments as disclosed herein.
In an embodiment, the ODVF interrupts can signal the system 100 of an
event/task to be serviced by the execution of an interrupt handler, which
may also be known as an interrupt service routine (ISR). The processor
module 208 can be configured to undergo a context switch to transition
15 from its current task to execute the interrupt associated with the interrupt
source 104. The processor module 208 can be configured to perform the
context switching when the interrupt or associated task time slice is expired
and the older task swaps with newer task. For example, in uni-processor
environment, the system 100 performs interrupt handling at end of context
20 switch and at the start of newly defined running task or process.
[0076] In multiprocessors environment, the system 100 performs
interrupt handling as soon as one processor is free at middle of context
switch. For example, if processors (P1, P2 and Pn) in the multiprocessor
environment performs context switch at a given time then the content
25 (CSSave[P1], CSSave[P2], and CSSave[Pn]) of all the processors need to be
saved in the registers of each processor. Each processor can save last
executing thread in a sequential manner to maintain atomicity of the data
along with reloading next task context and thread context (CSReload[P1],
CSReload[P2], and CSReload[Pn]) on to the processors P1, P2, and Pn,
26/55
respectively. Here, the target processor (for example, Pj) can include
interrupt affinity with the ODVF controller interrupt. For example, the first
processor to perform the CSSave[Pj interrupt affinity] when saving current
task context and thread context can be the last processor to reloading next
task context and thread context CSReload[Pj interrupt affinity] on to the P5 j
interrupt affinity processor. Similarly, the sequence can be represented as
CSSave[Pj interrupt affinity], CSSave[P1], CSSave[P2], and CSSave[Pn], and
CSReload[Pn] CSReload[P2], CSReload[P1], and CSReload[Pj interrupt affinity].
Further, at intermediate time, the Pj interrupt affinity processor is idle (not
10 performing any work) and the present invention includes allowing the
system to utilize the idle time of the Pj interrupt affinity processor for
processing the ODVF BUS controller ISR. Furthermore, the ODVF BUS
controller ISR can include jumps to the ISR which can be predicted using
the interrupt prediction matrix. Thus, unlike conventional systems, reducing
15 total number of context switch required through the system 100. The
system 100 can be configured to perform the context switch using the
interrupt prediction matrix information to efficiently manage the context
switching between the interrupts. Such a prediction-based model can
reduces the system cost and optimize the real-time performance of the
20 overall system 100.
[0077] The ODVF INT module 310 can be configured to implement
the interrupt scheduling logic using the interrupt prediction matrix 308 to
schedule the interrupts. For example, as shown in the FIG. 11A, the tasks 1-
N is represented as Ta0-TaN. Between the context switch of two tasks, the
25 ODVF_BUS.INT and ODVF controller interrupt can be scheduled. The
ODVF controller module 206 can be configured to include interfaces to the
ISR of the interrupt source(s) 104. In an embodiment, the timing signal at
which the interrupt source 104 generates the interrupt can be stored in the
interrupt prediction matrix 308 (as described in the FIG. 9). The interrupt
27/55
prediction matrix 308 can provide the time instant at which a particular
ODVF interrupt call should be included in the ODVF_BUS ISR. Based on
the information present in the interrupt prediction matrix 308 and the Walsh
function, the ODVF INT module 310 can be configured to schedule
interrupts to be processed by the processor. In an embodiment, if th5 e
interrupt handler of the ODVF is not recently occur (for example, there is
no data transfer completion interrupt occurs) then the ISR can be removed
from the body of the ODVF bus interrupt vector (even if it is found in the
Walsh function at that time). In an embodiment, if the interrupt source (for
10 example, the ODVF-1) needs a higher/faster frequency Walsh function and
the fast Walsh function available (which may not be used by the designated
interrupt source (for example, ODVF-2) then the ODVF-1 can be
interchange faster Walsh function with designated ODVF-2 until the
designated ODVF-2 can wake-up and request for the transfer.
15 [0078] FIG. 11B is a timing diagram 1102 for the interrupt task
scheduling logic described in the FIG. 11A, according to embodiments as
disclosed herein. The timing between the interrupts can be calculated using
equation TIJ =Φ (Wt, Bit rate frequency), where Wt is the Walsh function,
bit-rate frequency is the data transfer device function, and Φ () is the
20 algorithm computable function.
[0079] In an embodiment, the ODVF controller module 206 can be
configured to use the Walsh function and the interrupt prediction matrix
308 to predict and schedule the interrupts. In an embodiment, the Walsh
function described herein can be an orthogonal basis of square-integral
25 functions on unit interval. The functions can take values -1 and +1 based on
the sub-intervals defined by dyadic fractions (also referred as dyadic
rational). In an embodiment, the function can be represented in any other
form. In an embodiment, the dyadic fraction can be a rational number,
whose denominator can be a power of two. For example, a number of the
28/55
form “a/2b”, where “a” is an integer and “b” is a natural number. In an
embodiment, the Walsh function can be defined using the binary digit
representations of real’s and integers. For example, for an integer k,
consider the binary digit representation k = k0 + k12+...+km2m. For some
integer m with ki equal to 0 or 1 and k is the gray code transform of j-1, th5 e
j-nth Walsh function at a point x with 0 ≤ x < 1 can be Walsh j(x) = (-
1)(k
0
x
0
+...k
m
x
m
). If x = x0/2+ x1/22 + x2/23+..., where again xi is 0 or 1.
[0080] Each ODVF.INT shown in the FIG. 11 can be represented
by one Walsh Function. A complete Walsh Matrix represents multiplexing
10 of all ODVF.INT on a particular platform, where each of them represented
the Walsh function. In an embodiment, different methods, known in the art,
can be used to generate Walsh function. For example, when the application
of the a, b, c, d ODVF is rubbed then following pattern of the interrupt can
be obtained:
15 Yideal (t) = a. [1 1 1 1]
+ b. [1 1 -1 -1]
+ c. [1 -1 -1 1]
+ d. [1 -1 1 -1] Where, Yideal (t) is the frequency of interrupt
(summation of all frequencies of the interrupt patterns).
20 [0081] In an example, ‘a’ can include lowest priority and always be
one because, it represent interrupt enable. “d” can include highest priority
and represent the symbolic software timer with adaptive time slice. The
adaptive time slice described herein can be the time between aji to a(j)(i+1).
The value “-1” and “1” represent last value read at end of time slice at
25 falling and rising edge of timer respectively.
[0082] Where “1” represent successful prediction of occurrence of
interrupt by the Walsh function or the ODVF.INT logic and -1 represent the
successful prediction of not occurrence of interrupt by the Walsh function
or the ODVF.INT logic. Further, the measurement can be done at the time
29/55
of context switch between the two tasks and effects execution of the
interrupt prediction logic to schedule the predicated interrupts. The above
exemplary matrix represents respective ODVF.INT value for complete
adaptive time slice in cyclic order.
[0083] FIG. 12A is a diagram 1200 illustrating an exemplar5 y
preemptive interrupt task scheduling logic, according to embodiments as
disclosed herein. In an embodiment, the interrupts can be preemptive,
allowing the processor to context switch the current task. The ODVF
controller module 206 can be configured to support preemptive transfer of
10 device data. The preemptive time of occurrence of the preemptive interrupt
can be stored in the interrupt prediction matrix 308. The ODVF INT
module 310 can be configured to implement the preemptive interrupt
scheduling logic using the interrupt prediction matrix 308 to schedule the
interrupts.
15 [0084] In an embodiment, if the interrupt source data can be
preemptive then the ODVF buffer module 202 can be configured copy the
data related to the recently most context switch to partial filled the buffer
and send to the ODVF task module 312 from the ODVF.INT module 310.
Thus, from the next context switch the complete filled buffer is transferred
20 to the ODVF task module 312 from the ODVF.INT module 310 according
to the Walsh function (including interrupt pattern). In an embodiment,
when the false prediction of interrupt or no prediction of the interrupt
happens (may be due to interrupt prediction mechanism become out of
sync), the resynchronize interrupt matrix value are used to predict the next
25 occurrence of the interrupt. Thus, the interrupt can be schedule at that
context switch and the ODVF.INT module 310 can be configured to copy
partial filled buffer to the ODVF task module 312 for further processing the
data.
30/55
[0085] For example, as shown in the FIG. 12A, the tasks 1-N is
represented as Ta0-TaN. Between the context switch of two tasks, the
ODVF_BUS.INT and ODVF controller interrupt is scheduled. The ODVF
controller module 206 can be configured to include interfaces to the ISR of
the interrupt source(s) 104. In an embodiment, the timing signal at whic5 h
the interrupt source 104 generates the interrupt can be stored in the
interrupt prediction matrix 308 (such as described in the FIG. 9). The
ODVF controller module 206 can be configured to provide maximum
preemptive to the preemptive tasks such that when the context switch is
10 performed ODVF INT module 310 can schedule the interrupt and the
ODVF controller module 206 can be configured to empty the data stored in
the ODVF buffer module 302. Further, the preemptive logic can transfer
the partially filled interrupt sources buffer to the system memory in
between the context switch time. Similarly, the system 100 can be
15 configured to handle delays of the interrupts.
[0086] FIG. 12B is a preemptive timing diagram 1202 for the
interrupt task scheduling logic described in the FIG. 12A, according to
embodiments as disclosed herein. In an embodiment, the ODVF controller
module 206 can be configured to use the Walsh function and the interrupt
20 prediction matrix 308 to predict and schedule the preemptive interrupts.
The preemptive timing between the interrupts can be calculated using
equation TIJPre =Φ(Wt, Bit rate frequency), where Wt is the Walsh
function, bit-rate frequency is the data transfer device function, and Φ() is
the algorithm computable function.
25 [0087] FIG. 13 is diagram 1300 illustrating the division of the
Orthogonal Device Vector Function (ODVF), according to embodiments as
disclosed herein. The ODVF can be divided into two modules namely, the
ODVF INT module 310, and the ODVF task module 312 respectively. The
31/55
division of the ODVF is done for effective prediction and execution of the
interrupts.
[0088] In an embodiment, the ODVF INT module 310 can be
configured to schedule the respective interrupt using the interrupt
prediction matrix 308 and the Walsh function. In an embodiment, th5 e
ODVF task module 312 can be configured to allow the various interrupt
sources 104 to follow real-time task criteria for processing the tasks
associated with the interrupts. The ODVF task module 312 can be
configured to calculate a Worst case execution time (WCET) and average
10 case execution time (ACET) for each tasks associated with the interrupts.
[0089] In an example, the calculation of the WCET for two tasks
(such as T1 and T2) is described. For a given context bound (CB) and an
interrupt driven program P= ODVF.TASK||T0||T1||T2||T3||… ||TN (where, T
represents the real-time task), a sequential program Pseq can be generated
15 which is paths equivalent to P up to the CB. If the interrupt recall is of
higher priority than
, i T if j > i
and that the main function is T0 then the
procedure iteratively replaces each Tj starting with j=N with a replacement
sequential program Tj, such that every interleaved path start with Tj and
may involve higher-priority tasks as a program pad in Tj. Thus, the
20 ODVF.TASK can be the desired sequential program Pseq. The sequential
program
i
j T
can update a set of dummy shared variables that track number
of context switches and the program locations at which context switch
occur. The below equation describes the determination of
i
j T
from TJ,
(assuming, the TJ is a sequence of k atomic statements).
1 2 3 ; ; ;..., j k 25 T ı S S S S
[0090] Thus, for each higher-priority task Ti, i> j, there are k+1
possible locations where it may be invoked with a possibility that it may
not interrupt Tj at all. In an embodiment, the possible switching points as
32/55
well as the choice of tasks can be encoded at the switching point using a
non-deterministic choice symbol "*". The non-deterministic choice symbol
can be replaced by any Boolean variable while generating symbolic paths
execution. Also, each invocation of the higher priority task increments a
global variable (C) that tracks the number of context switches. In a5 n
example, the C can be initialized to 0 when P begins execution and a higher
priority task can interrupt a lower priority task only if Ca then it can be possible
10 that the main function of P is interrupted twice before terminating. Thus,
the system set CB=2, regenerate the corresponding sequential program, and
re-compute the WCET. The system can compare the TimeWCET with 2a. If
the system determines that the TimeWCET < 2a, then the system can
terminate with CB =2, else the system can increase CB by one and repeat
15 the procedure again. Generally, when CB=k, the system compare the
TimeWCET with ka and terminates when TimeWCET < ka or else increase the
CB to k+1. If the time taken by an ISR (in the presence of the higher
priority interrupts) is less than the minimum inter-arrival time of interrupts
then the system ensures to terminate with finite context bound.
20 [0093] In an embodiment, the ODVF base path analysis and
predictions is described. In an example, the sequential program Pseq (which
is sequential form of the ODVF) can generate the basis paths for the
program along with the corresponding test cases. The test case described
herein can include, for example, an assignment to program variables as well
25 as to the non-deterministic choice variables that indicate where the tasks are
interrupted and by which higher priority task. The system can execute the
test cases within a harness that triggers interrupts at the right locations as
indicated by the test case. The harness described herein can be specific to
34/55
each platform, involving the use of a few inline assembly instructions at
each interrupt point (location).
[0094] Further, the ODVF task module 312 can be configured to
make interrupt device vector functions compatible with the real-time
operating system. The ODVF task module 312 can be configured t5 o
analyze the WCET and ACET using the ODVF program scheduled (not till
main scheduler program). Each ODVF program can be represented by
sequentialize Tj program path (with at most CB-1 context switches). After
converting the previous approach, the ODVF task module 312 can be
10 configured to compute the WCET and ACET of the ODVF. In an
embodiment, both times should not be greater than previous approach. For
ODVF program, if the TimeWCET is less than α, then complete ODVF
before a second interrupt is raised. If the TimeWCET ≥ α, it may be possible
that the ODVF program is computed twice before terminating. Thus, the
15 ODVF task module 312 sets CB=2 and regenerates corresponding
sequential program. In an example, when CB=k, the system compare the
TimeWCET with k α and terminate when the TimeWCET