Memory management in embedded systems with dynamic object instantiation Number:6,820,184 from the United States Patent and Trademark Office (PTO) owispatent

Title: Memory management in embedded systems with dynamic object instantiation

Abstract: A system and method is provided for enabling the reuse of algorithms in multiple application frameworks with no alterations required of the algorithm once it is developed. An inverted memory allocation mechanism enables various algorithm modules to be integrated into a single application without modifying the source code of the algorithm modules. A plurality of algorithm modules is combined with a framework to form the software program. Each of the plurality of algorithm modules has a memory interface which responds to a memory allocation inquiry with memory usage requirements of an instance of the algorithm module. The software program is then loaded on a hardware platform and executed. During execution, the framework sends a query to the memory interface of each of the plurality of algorithm modules to request memory usage requirements for each instance of each of the plurality of algorithm modules. A response is then sent from the memory interface of each algorithm module identifying memory usage requirements for each instance of the algorithm module. The framework then allocates a portion of memory to each algorithm module to instantiate each instance in accordance with the memory usage requirement identified by the memory interface of each algorithm module. Thus, each instance of the plurality of algorithm modules is instantiated and allocated memory dynamically.

Patent Number: 6,820,184 Issued on 11/16/2004 to Russo,   et al.

---

Inventors:	Russo; David A. (Santa Barbara, CA); Frankel; Robert E. (Goleta, CA)
Assignee:	Texas Instruments Incorporated (Dallas, TX)
Appl. No.:	355924
Filed:	January 31, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	666044	Sep., 2000	6546477

---

Current U.S. Class:	711/170 ; 717/100
Field of Search:	711/170 717/100

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5146565		September 1992		Blanck et al.
	5247674		September 1993		Kogure
	5491808		February 1996		Geist, Jr.
	5590271		December 1996		Klinker
	5701506		December 1997		Hosotani
	5784699		July 1998		McMahon et al.
	5836014		November 1998		Faiman, Jr.
	5930827		July 1999		Sturges
	5970245		October 1999		Poteat et al.
	6070202		May 2000		Minkoff et al.
	6081665		June 2000		Nilsen et al.
	6134181		October 2000		Landry
	6308315		October 2001		Dice et al.
	6341368		January 2002		Deans
	6381735		April 2002		Hunt
	6425120		July 2002		Morganelli et al.
	6446253		September 2002		Mellmer
	6505344		January 2003		Blais et al.
	6546477		April 2003		Russo et al.

Other References

Rob van Ommering , et al.; The Koala Component Model for Consumer Electronics Software,IEEE Computer, vol. 33, Issue 3, Mar. 2000, pp. 78-85. . Zorn et al; Evaluating Models of Memory Allocation; ACM Transactions on Modeling and Computer Simulation; vol. 4, No. 1, Jan. 1994, pp. 107-131; ACm 1049-3301/94/0100-0107. . Yingchun Zhu et al; Communication Optimizations for Parallel C Programs; ACM; 1998; pp. 199-211. . Chang et al.; Measuring Dynamic Memory Invocations in Ojbect-oriented Programs; IEEE 1999; pp. 268-274. . Van Ommering, Rob, et al; The Koala Component Model for Consumer Electronics Software; IEEE Computer, vol. 33, Issue 3, Mar. 2000; pp. 78-85. . David K. Every; Reentrant, What is it, why does it matter?; Feb. 1999. . Jack G. Ganssle; Writing Relocatable Code; 1992. . Microsoft Press; Microsoft Press Computer Dictionary, Third Edition; 1997; p 484. . Rob McGregor; Practical C++; Que Corporation; 1999..

Primary Examiner: Nguyen; Hiep T.
Attorney, Agent or Firm: Marshall, Jr.; Robert D. Brady, III; W. James Telecky, Jr.; Frederick J.

---

Parent Case Text

---

CROSS REFERENCE TO RELATED APPLICATIONS

This application is a continuation of Ser. No. 09/666,044 filed Sep. 20, 2000, which claims priority to provisional application Ser. No. 60/154,777, filed Sep. 20, 1999, provisional application Ser. No. 60/154,657 filed Sep. 20, 1999, and provisional application Ser. No. 60/154,656 filed Sep. 20, 1999, and is related to application Ser. No. 09/667,393 now U.S. Pat. No. 6,691,298 and application Ser. No. 09/666,629.

---

Claims

---

What is claimed is:

1. A method of executing algorithms in a framework comprising the steps of: activating an instance of an algorithm module in accordance with an activation interface of the algorithm module; causing instructions of the instance to be executed; and deactivating the instance in accordance with a deactivation interface of the algorithm module.

2. The method of claim 1 further comprising the step of allocating portions of memory to the algorithm module in accordance with a set of memory usage requirements identified by a memory interface of the algorithm module.

3. The method of claim 2 wherein the set of memory usage requirements comprises alignments, sizes, and types of memory.

4. The method of claim 3, wherein the step of allocating further comprises allocating a first portion of the required memory in persistent memory and a second portion of the required memory in shared scratch memory.

5. The method of claim 3 wherein the step of allocating further comprises allocating a portion of the required memory in persistent memory.

6. The method of claim 3 wherein the step of allocating further comprises allocating a portion of the required memory in shared scratch memory.

7. The method of claim 4 wherein the step of activating further comprises moving data from the persistent memory allocated to the algorithm module to the shared scratch memory allocated to the algorithm module; the step of executing further comprises using the shared scratch memory during execution of the instance; and the step of deactivating further comprises moving data from the shared scratch memory to the persistent memory.

8. The method of claim 1 further comprising the steps of: sending a query from the framework to the memory interface of the algorithm module to request the set memory usage requirements for instances of the algorithm module; and receiving a response from the memory interface of the algorithm module identifying the set of memory usage requirements for instances of the algorithm module.

9. The method of claim 8 wherein the set of memory usage requirements comprises alignments, sizes, and types of memory.

10. The method of claim 9, wherein the step of allocating further comprises allocating a first portion of the required memory in persistent memory and a second portion of the required memory in shared scratch memory.

11. The method of claim 10 wherein the step of activating further comprises moving data from the persistent memory allocated to the algorithm module to the shared scratch memory allocated to the algorithm module; the step of executing further comprises using the shared scratch memory during execution of the instance; and the step of deactivating further comprises moving data from the shared scratch memory to the persistent memory.

12. A digital system, comprising: a microprocessor with a central processing unit (CPU); a memory connected to the CPU; and a program stored in the memory, the program comprising: a framework linked to each of a plurality of algorithms modules, wherein the framework is operable to query a memory interface in each of the plurality of algorithms modules and wherein the memory interface is operable to respond with a set of memory usage requirements of the algorithm module when the memory interface is queried by a framework, such that when the software program is executed by the CPU, execution comprises the steps of: sending a query from the framework to the memory interface of each of the plurality of algorithm modules to request the set of memory usage requirements for each instance of each of the plurality of algorithm modules; receiving a response from the memory interface of each algorithm module identifying the set of memory usage requirements of each instance of the algorithm module; and allocating a portion of memory to each algorithm module to instantiate each instance in accordance with the set of memory usage requirements identified by the memory interface of each algorithm module.

13. The digital system of claim 12 in which each of the plurality of algorithm modules further includes an activation interface and a deactivation interface and execution further comprises the steps of activating an instance of an algorithm module in accordance with the activation interface of the algorithm module; causing instructions of the instance to be executed; and deactivating the instance in accordance with the deactivation interface of the algorithm module.

14. A digital system, comprising: a microprocessor with a central processing unit (CPU); a memory connected to the CPU; and a program stored in the memory, the program comprising: a framework linked to each of a plurality of algorithms modules, wherein the framework is operable to facilitate the execution of the plurality of algorithm modules and each algorithm module of the plurality of algorithm modules includes an activation interface and a deactivation interface, such that when the software program is executed by the CPU, the framework performs a method comprising the steps of: activating an instance of an algorithm module in accordance with the activation interface of the algorithm module; causing instructions of the instance to be executed; and deactivating the instance in accordance with the deactivation interface of the algorithm module.

15. The digital system of claim 14 in which each of the plurality of algorithm modules further includes a memory interface, wherein the memory interface is operable to provide a set of memory usage requirements of the algorithm module to the framework and the method performed by the framework further comprises the step of allocating portions of memory to the algorithm module in accordance with the set of memory usage requirements provided by the memory interface of the algorithm module.

16. The digital system of claim 15 in which the method performed by the framework further comprises the steps of: sending a query to the memory interface of an algorithm module to request the set of memory usage requirements for instances of the algorithm module; and receiving a response from the memory interface of the algorithm module identifying the set of memory usage requirements for instances of the algorithm module.

17. A computer readable medium containing a functional framework, wherein the framework comprises a component model including a device independent I/O sub-system and is for calling one or more algorithms, wherein the framework provides a method of facilitating execution of algorithms comprising the steps of: providing functionality to activate an instance of an algorithm module in accordance with an activation interface of the algorithm module; providing functionality to cause instructions of the instance to be executed; and providing functionality to deactivate the instance in accordance with a deactivation interface of the algorithm module.

18. The computer readable medium of claim 17 wherein the method provided by the framework further comprises the step of providing functionality to allocate portions of memory to the algorithm module in accordance with a set of memory usage requirements identified by a memory interface of the algorithm module.

19. The computer readable medium of claim 18 wherein the method provided by the framework further comprises the steps of: providing functionality to send a query from the framework to the memory interface of the algorithm module to request a set of memory usage requirements for instances of the algorithm module; and providing functionality to receive a response from the memory interface of the algorithm module identifying the set of memory usage requirements for instances of the algorithm module.

20. A method for creating an algorithm module to be executed in a framework comprising the steps of: implementing memory allocation functionality corresponding to a memory allocation standard of the framework; implementing instance activation functionality corresponding to an instance activation standard of the framework; implementing instance deactivation functionality corresponding to an instance activation standard of the framework; and encapsulating an algorithm with the standard memory allocation functionality, the instance activation functionality, and the instance deactivation functionality.

---

Description

---

Appendix A containing a computer program listing is submitted on two identical compact disks. Each compact disk contains the file Appendix A.txt. The file was created on Jan. 23, 2003, and is 40 KB bytes in size. Appendix A is hereby incorporated by reference.

TECHNICAL FIELD OF THE INVENTION

The present invention relates to embedded software systems, and more particularly to component and object-oriented programming models for embedded systems.

BACKGROUND OF THE INVENTION

Advances in digital signal processor (DSP) technology in the application areas of telephony, imaging, video, and voice are often results of years of intensive research and development. For example, algorithm standards for telephony have taken years, to develop. The implementation of these DSP algorithms is often very different from one application system to another because systems have, for example, different memory management policies and I/O handling mechanisms. Because of the lack of consistent system integration or programming standards, it is generally not possible for a DSP implementation of an algorithm to be used in more than one system or application without significant reengineering, integration, and testing.

Digital Signal Processors (DSPs) are often programmed like "traditional" embedded microprocessors. That is, they are programmed in a mix of C and assembly language, directly access hardware peripherals, and, for performance reasons, almost always have little or no standard operating system support. Thus, like traditional microprocessors, there is very little use of Commercial Off-the-Shelf (COTS) software components for DSPs.

However, unlike general-purpose embedded microprocessors, DSPs are designed to run sophisticated signal processing algorithms and heuristics. For example, they may be used to detect DTMF digits in the presence of noise, to compress toll quality speech by a factor of 20, or for speech recognition in a noisy automobile traveling at 65 miles per hour.

Such algorithms are often the result of many years of doctoral research. However, because of the lack of consistent standards, it is not possible to use an algorithm in more than one system without significant reengineering. Since few companies can afford a team of DSP PhDs and the reuse of DSP algorithms is so labor intensive, the time-to-market for a new DSP-based product is measured in years rather than months.

Most modern DSP system architectures can be logically partitioned into algorithms, core run-time support and a framework that integrates the algorithms with the hardware and software comprising the system. The framework defines a component model with which the algorithms must comply. The framework includes a device independent I/O sub-system and specifies how algorithms interact with this sub-system. For example, does the algorithm call functions to request data or does the framework call the algorithm with data buffers to process? The framework also defines the degree of modularity within the application; i.e., what components can be replaced, added, removed, and when components can be replaced (compile time, link time, or real-time). Unfortunately, for performance reasons, many DSP system architectures do not enforce a clear line between algorithm code and the framework. Thus, it is not possible to easily use an algorithm in more than one system.

Even within the telephony application space, there are a number of different frameworks available and each is optimized for a particular application segment; e.g., large volume client-side products and low volume high-density server-side products. Given the large number of incompatibilities between these various frameworks and the fact that each framework has enjoyed success in the market, any model for algorithm reuse should ideally make few requirements on existing frameworks.

Careful inspection of the various frameworks in use reveals that, at some level, they all have "algorithm components". While there are differences in each of the frameworks, the algorithm components share many common attributes: algorithms are C callable; algorithms are reentrant; algorithms are independent of any particular I/O peripheral; and, algorithms are characterized by their memory and instruction processing rate (MIPS) requirements. In approximately half of the known available frameworks, algorithms are also required to simply process data passed to the algorithm. The others assume that the algorithm will actively acquire data by calling framework-specific hardware independent I/O functions. Generally, algorithms are designed to be independent of the I/O peripherals in the system.

Given the similarities between the various frameworks, a need has arisen to create a model permitting simple reuse at the level of the algorithm. Moreover, there is real benefit to the framework vendors and system integrators from such a model: algorithm integration time will be reduced; it will be possible to easily comparison shop for the "best" algorithm; and more algorithms will be available.

A huge number of DSP algorithms are needed in today's marketplace, including modems, vocoders, speech recognizers, echo cancellation, and text-to-speech. It is not easy (or even possible) for a product developer who wants to leverage this rich set of algorithms to obtain all the necessary algorithms from a single source. On the other hand, integrating algorithms from multiple vendors is often impossible due to incompatibilities between the various implementations. To break this catch-22, algorithms from different vendors must inter-operate.

Dozens of distinct third-party DSP frameworks exist in the telephone vertical market alone. Each vendor has hundreds and sometimes thousands of customers. Yet, no one framework dominates the market. To achieve the goal of algorithm reuse, the same algorithm must be usable in all frameworks with minor impact on the framework implementation.

Marketplace fragmentation by various frameworks has a legitimate technical basis. Each framework optimizes performance for an intended class of systems. For example, client systems are designed as single-channel systems with limited memory, limited power, and lower-cost DSPS. As a result, they are quite sensitive to performance degradation. Server systems, on the other hand, use a single DSP to handle multiple channels, thus reducing the cost per channel. As a result, they must support a dynamic environment. Yet, both client-side and server-side systems may require exactly the same vocoders.

Algorithms must be deliverable in binary form both to protect the vendor's intellectual property and to improve the reusability of the algorithm. If source code were required, all frameworks would require re-compilation. This would destabilize the frameworks and version control for the algorithms would be close to impossible.

Each particular implementation of a system (such as a speech detector) represents a complex set of engineering trade-offs between code size, data size, MIPS, and quality. Moreover, depending on the system designed, the system integrator may prefer an algorithm with lower quality and a smaller footprint to one with higher quality detection and a larger footprint (such as an electronic toy doll vs. a corporate voice mail system). Thus, multiple implementations of exactly the same algorithm sometimes make sense. There is no single best implementation of many algorithms.

Unfortunately, the system integrator is often faced with choosing all algorithms from a single vendor to ensure compatibility between the algorithms and to minimize the overhead of managing disparate APIs. Moreover, no single algorithm vendor has all the algorithms for all their customers. The system integrator is, therefore, faced with selecting a vendor that has "most" of the required algorithms and negotiating with that vendor to implement the remaining algorithms.

Most modern DSP hardware architectures include both on-chip data memory and off-chip memory. The performance difference between these is so large that algorithm vendors design their code to operate within the on-chip memory as much as possible. Since the performance gap is expect to increase dramatically in the next 3-5 years, this trend will continue for the foreseeable future.

While the amount of on-chip data memory in a given DSP architecture may be adequate for each algorithm in isolation, the increased number of MIPS available on modern DSPs enables the creation of complex software systems that perform multiple algorithms concurrently on a single chip. There may not be enough on-chip memory to allow all algorithms to have their full, required complement of data memory resident in on-chip memory concurrently. There is a need for a method to permit efficient sharing of this resource among the algorithms. Generally, prior art methods for memory sharing in a complex system have required that an algorithm be partially or substantially rewritten each time it was used in a new framework. This situation makes it very costly, both in time and money, for a third party algorithm vendor to provide algorithms for multiple frameworks.

SUMMARY OF THE INVENTION

An illustrative embodiment of the present invention seeks to provide a system and method for enabling the reuse of algorithms in multiple application frameworks with no alterations required of the algorithm once it is developed. Aspects of the invention are specified in the claims.

In an embodiment of the present invention, an algorithm component model enables many of the benefits normally associated with object-oriented and component-based programming but with little or no overhead. An inverted memory allocation mechanism enables various algorithm modules to be integrated into a single application without modifying the source code of the algorithm modules. The embodiment also includes naming conventions to prevent external name conflicts, a uniform method for initializing algorithms, a uniform trace and diagnostic interface, and a uniform packaging specification.

In this embodiment of the present invention, a method is provided for managing memory usage in a software program having a framework and a plurality of algorithm modules.

The plurality of algorithm modules is combined with the framework to form the software program, wherein each of the plurality of algorithm modules has a memory interface which responds to a memory allocation inquiry with memory usage requirements of an instance of the algorithm module. The software program is then loaded on a hardware platform and executed. During execution, the framework sends a query to the memory interface of each of the plurality of algorithm modules to request memory usage requirements for each instance of each of the plurality of algorithm modules. A response is then sent from the memory interface of each algorithm module identifying memory usage requirements for each instance of the algorithm module. The framework then allocates a portion of memory to each algorithm module to instantiate each instance in accordance with the memory usage requirement identified by the memory interface of each algorithm module. Thus, each instance of the plurality of algorithm modules is instantiated and allocated memory dynamically.

Another embodiment of the present invention is a software program that has a plurality of algorithm modules linked to a framework. Each of modules includes a memory interface that is operable to respond with a memory usage requirements of the algorithm when the memory interface is queried by a framework. The framework allocates memory to each instance of each algorithm module in accordance to a response to the query from each module.

Another embodiment of the present invention is a digital system with a program stored in non-volatile memory. The software program has a plurality of algorithm modules linked to a framework. Each of modules includes a memory interface that is operable to respond with memory usage requirements of the algorithm when the memory interface is queried by a framework. The framework allocates memory to each instance of each algorithm module in accordance to a response to the query from each module.

In another embodiment, the digital system is a cellular telephone.

In the following description, specific information is set forth to provide a thorough understanding of the present invention.

These and other features of the invention that will be apparent to those skilled in the art from the following detailed description of the invention, taken together with the accompanying drawings.

DESCRIPTION OF THE DRAWINGS

FIG. 1A is a block diagram illustrating the architecture of an embedded system with a framework and multiple algorithm modules that embodies the present invention;

FIG. 1B is a block diagram illustrating a development system that is used to create an embedded system;

FIG. 2 is a hierarchical model illustrating elements to be considered in creating a component model for embedded systems;

FIG. 3 is a block diagram of a component model for embedded systems with a module interface that embodies the present invention;

FIG. 4 is a block diagram illustrating the concept of managing an object using a module interface according to FIG. 3;

FIG. 5 is a code listing illustrating example code for a very simple module of FIG. 4;

FIG. 6 is a flow chart illustrating how a framework in a component model of FIG. 3 calls functions in a module;

FIGS. 7A, 7B and 7C together are a code listing illustrating code for an example of an abstract algorithm instance (IALG) interface for the component model of FIG. 3;

FIG. 8 is a flow graph illustrating the use of a memory interface function of an algorithm module that is an embodiment of the present invention;

FIG. 9 is a code listing with code fragments to illustrate how a framework may use the same style of parameter passing whether passing generic parameters or implementation-specific parameters to an algorithm module within the flow of FIG. 8;

FIG. 10 is a code listing illustrating generic create and delete functions a framework may use to create run-time instances of an algorithm in the component model of FIG. 3;

FIG. 11 is a code listing illustrating an optional activate/deactivate feature for a memory interface to enable memory sharing if a framework supports it for the flow of FIG. 8;

FIG. 12 is a code listing with example implementations of the activate and deactivate functions of FIG. 11;

FIG. 13 is a code listing of an example implementation of a function algAlloc( ) that returns a table of memory records that describe the size, alignment, type and memory space of all buffers required by an algorithm instance in the flow of FIG. 8;

FIG. 14 is a code listing of an example implementation of a function algControl( ) to allow a framework to call a specific function in an algorithm;

FIG. 15 is a code listing of an example implementation of a function algFree( ) that returns a table of memory records that describe the base address, size, alignment, type, and memory space of all buffers previously allocated for an algorithm instance in the flow of FIG. 8;

FIG. 16 is a code listing of an example implementation of a function algInit( ) that performs all initialization necessary to complete the run-time creation of an algorithm's instance object in the flow of FIG. 8;

FIG. 17 is a code listing of an example implementation of a function algMoved( ) that performs any reinitialization necessary to insure that all internal data references are recomputed after a framework relocates an algorithm at run-time in the flow of FIG. 8;

FIG. 18 is a code listing of an example implementation of a function algNumAlloc( ) that allows a framework to determine the maximum number of memory requests an algorithm instance may make;

FIG. 19 is a code listing of an example a uniform trace and diagnostic (IRTC) interface for an algorithm module in an alternative embodiment of the component model of FIG. 3;

FIGS. 20A and 20B together are a flow graph of a method for dynamic object instantiation with the component model of FIG. 3;

FIG. 21 is a block diagram illustrating an architecture of a digital system with several different memory spaces and types of memory that can be requested and allocated for use by algorithm module instances in an embodiment of the present invention;

FIG. 22 is an illustration of various types of memory, such as persistent memory and scratch memory, which can be requested by algorithm instances within the digital system of FIG. 21;

FIG. 23A is a block diagram of an example algorithm module that includes both an IALG interface and an IRTC interface;

FIG. 23B is a block diagram of another example algorithm module that embodies the present invention and that illustrates a function calling interface, an IALG interface and an IRTC interface;

FIG. 24 is a flow chart for another embodiment of the present invention that is a method of converting an existing algorithm to an algorithm module so that it may be used in the flow of FIG. 8;

FIG. 25 is a flow graph illustrating the use of a memory interface function of an algorithm module that has been instantiated at "design time";

FIGS. 26A, 26B and 26C are flow graphs that, taken together, illustrate another embodiment of the present invention in which algorithm instances are instantiated at "design time" of a application program and all code for interfaces that will not be needed in a static system is excluded; and

FIG. 27 is an example digital system that embodies the present invention, this example being a wireless telephone.

Corresponding numerals and symbols in the different figures and tables refer to corresponding parts unless otherwise indicated.

DETAILED DESCRIPTION OF THE INVENTION

Many modern DSP software system architectures can be partitioned along the lines depicted in FIG. 1A. Algorithms 105 are "pure" data transducers; i.e., they simple take input data buffers 101 and produce some number of output data buffers 102. Core run-time support 103 includes functions that copy memory, functions to enable and disable interrupts, and real-time debugging aids. Framework 104 is the "glue" that integrates algorithms 105 with real-time data sources 101 and sinks 102 using core run time support 103, to create a complete DSP sub-system. Framework 104 in essence defines a component model with which algorithms 105 must comply. Framework 104 interacts with any real-time peripherals (including other processors in the system) and defines the I/O interfaces for the algorithms 105.

It has now been discovered that several technical issues have prevented the creation of such a method. One major issue is that algorithm implementations to date have been responsible for managing their own memory usage. If an algorithm is to be used in a variety of applications, the framework rather than the algorithm must make decisions about memory usage and preemption. This is referred to as an inverted memory protocol herein.

The algorithms and framework are implemented using a software development system that provides an assembler, compiler, linker, debugger, and other tools. Associated with the compiler will be language run-time support that will be incorporated into an application when it is constructed with the linker. For DSP software development, the development system may also include a DSP operating system to be used when creating an embedded software system. This operating system would be incorporated into the embedded software system when it is constructed with the linker. Once the embedded software system is constructed, it is downloaded onto a target DSP hardware system to be debugged. A debug environment in the software development system connects high level debugging software executing on a host computer to a low level debug interface supported by a target device.

FIG. 1B illustrates a software development system connected to a target hardware system that contains a DSP. This development environment has three parts: development host 106, access adapter 107, and target system 108.

Development Host 106 is a computer, for example a PC, running a DSP specific software debugger as one of its tasks. The debugger allows the user to issue high level commands such as "set breakpoint at location 0.times.6789", "step one instruction" or "display the contents of memory from 0.times.1000 to 0.times.1048". An example host system is described fully in U.S. Pat. No. 5,329,471.

Access Adapter 107 is a hardware component that connects development host 106 to a target system. It utilizes one or more hardware interfaces and/or protocols to convert messages created by user interface commands to the debug command. This component could be a Texas Instruments XDS 510WS controller, for example, connected to the target system debug interface and to the PC through a SCSI port. An alternate configuration is a Texas Instruments XDS 510 controller installed in a PC connected to the target system debug interface. An example access adapter is described fully in U.S. Pat. No. 5,329,471.

Target System 108 is comprised of one or more DSPs. The DSP(s) contain hardware designed explicitly to ease the chore of debugging. It is the lowest element of the system debug environment. The DSP debug facilities allow the user to control the program execution, examine the state of the system, memory, and core resources in both real-time and stop mode debug modes. Target System 108 may be a cellular telephone, for example. Once a software program is written, compiled, linked and loaded onto the target system, it is then debugged and refined. Advantageously, a software program that embodies the present invention can be developed in a manner that minimizes debugging and redesign.

By enabling system integrators to "plug-replace" one algorithm for another, the time to market is reduced because the system integrator can choose algorithms from multiple vendors. A huge catalog of inter-operable parts from which any system can be built and can be easily created.

These algorithms must meet the following requirements:

Algorithms from multiple vendors can be easily integrated into a single system.

Algorithms are framework agnostic. That is, the same algorithm can be efficiently used in virtually any application or framework.

Algorithms can be deployed in purely static as well as dynamic run-time environments.

Algorithms can be deployed in preemptive or non-preemptive multitasking environments.

Algorithms can be distributed in binary form.

Integration of algorithms does not require recompilation of the client, application; re-configuration and re-linking may be required, however.

Table 1 defines various terms that will be used herein.

TABLE 1 Term Definitions Abstract An interface defined by a C header whose functions are specified by a structure of function Interface pointers. By convention these inter-face headers begin with the letter "i" and the interface name begins with "I". Such an interface is abstract because, in general, many modules in a system implement the same abstract interface; i.e., the interface de-fines abstract operations supported by many modules. Algorithm: Technically, an algorithm is a sequence of operations, each chosen from a finite set of well- defined operations (for example, computer instructions), that halts in a finite time, and computes a mathematical function. In this specification, however, we allow algorithms to employ heuristics and do not require that they always produce a correct answer. API Acronym for application programming interface. A specific set of constants, types, variables, and functions used to programmatically interact with a piece of software. Client: The term client denotes any piece of software that uses a function, module, or interface. For example, if the function a() calls the function b(), a() is a client of b(). Similarly, if an application App uses module MOD, App is a client of MOD. Concrete An interface defined by a C header whose functions are implemented by a single module Interface within a system. This is in contrast to an abstract interface where multiple modules in a system can implement the same abstract interface. The header for every module defines a concrete interface. Critical Section: A critical section of code is one in which data that can be accessed by other threads are inconsistent. At a higher level, a critical section is a section of code in which a guarantee you make to other threads about the state of some data may not be true. If other threads can access these data during a critical section, your pro-gram may not behave correctly. This may cause it to crash, lock up, or produce incorrect results. In order to insure proper system operation, other threads are denied access to inconsistent data during a critical section (usually through the use of locks). Poor system performance could be the result if some of your critical sections are too long. Endian: Refers to which bytes are most significant in multi-byte data types. In big-endian architectures, the leftmost bytes (those with a lower ad-dress) are most significant. In little- endian architectures, the rightmost bytes are most significant. HP, IBM, Motorola 68000, and SPARC systems store multi-byte values in big-endian order, while Intel 80x86, DEC VAX, and DEC Alpha systems store them in little-endian order. Internet standard byte ordering is also big-endian. The TMS320C6000 is bi-endian because it supports both systems. Frame: Algorithms often process multiple samples of data at a time, referred to as a frame. In addition to improving performance, some algorithms require specific minimum frame sizes to operate properly. Framework: Part of an application that is designed to remain invariant while selected software components are added, removed, or modified. Very general frameworks are sometimes described as application-specific operating systems Instance: The specific data allocated in an application that defines a particular object. Interface: A set of related functions, types, constants, and variables. An interface is often specified with a C header file. Interrupt The maximum time between when an interrupt occurs and its corresponding interrupt service Latency: routine (ISR) starts executing. Method: A synonym for a function that is part of an interface. Module: A module is an implementation of one (or more) interfaces. In addition, all modules follow certain design elements that are common to all XDAIS compatible software components. Roughly speaking, a module is a C language implementation of a C++ class. Multithreading: Multithreading is the management of logically concurrent threads within the same program or system. Most operating systems and modern computer languages also support multithreading. Preemptive: A property of a scheduler that allows one task to asynchronously interrupt the execution of the currently executing task and switch to another task. The interrupted task is not required to call any scheduler functions to enable the switch. Reentrant A property of a program or a part of a program in its executable version, that can be entered repeatedly, or can be entered before previous executions have been completed. Each execution of such a pro-gram is independent of all other executions. Scratch Memory Memory that can he overwritten without loss; i.e., prior contents need not he saved and restored after each use. Scratch Register: A register that can be overwritten without loss; i.e., prior contents need not be saved and restored after each use. Thread The program state managed by the operating system that defines a logically independent sequence of program instructions. This state may be as small as the program counter (PC) value but often includes a large portion of the CPUs register set.

FIG. 2 demonstrates the elements that should be considered in creating a component model for embedded systems. Level 1201 contains programming guidelines that apply to all algorithms on all DSP architectures regardless of application area. Almost all recently developed algorithms follow these common sense guidelines but they are formalized in an embodiment of the present invention, as they must be followed for the embodiment to work successfully.

Level 2202 describes software techniques to enable all algorithms to operate harmoniously within a single system. The present invention is most to concerned with this level, presenting solutions to technical problems that previously made the creation of algorithms usable across multiple frameworks impossible.

Level 3203 deals with guidelines for specific families of DSPs. Level 4204 is concerned with various vertical markets. These levels are outside the scope of the present invention as they do not need to be addressed in order to implement the present invention

For algorithms to satisfy the minimum requirements of reentrancy, I/O peripheral independence, and debuggability, they must rely on a core set of services that is always present. Since most algorithms are still produced using assembly language, many of the services provided by this core must be accessible and appropriate for assembly language.

In an embodiment of the present invention, the core set of services includes a subset of a DSP operating system together with some additions to support atomic modification of control/status registers. It also includes a subset of standard C language run-time support libraries; e.g., memcpy, strcpy, etc.

The DSP operating system is a collection of twelve modules:

CLK--On-Chip Timer Manager

GBL--Global Settings Manager

HST--Host I/O Manager

HWI--Hardware Interrupt Manager

IDL--Idle Function Manager

LOG--History Log Manager

MEM--Memory Manager

PIP--Data Pipe Manager

PRD--Periodic Function Manager

RTC--Real-Time Trace Manager

SWI--Software Interrupt Manager

STS--Statistics Accumulator Manager

Of these modules, only SWI, PRD, and IDL are directly related to thread scheduling. Table 2 describes which operations are callable. Unless otherwise noted, any operation that does not appear in this table must not be called.

TABLE 2 Callable Operations Allowed or Mod- Disallowed ule Typical Function in Category Notes allowed CLK CLK_gethtime, CLK_getltime 1 allowed HST HST_getpipe 1 allowed HWI HWI_disable, HWI_enable, HWI_restore 2 disallowed HWI HWI_enter, HWI_exit allowed LOG LOG_event, LOG_printf, LOG_error, etc. 1 allowed PIP PIP_alloc, PIP_get, PIP_put, PIP_free 1 allowed PRD PRD_getticks disallowed PRD PRD_start, PRD_tick allowed RTC RTC_disable, RTC_enable, RTC_query 3 allowed STS STS_add, STS_delta, STS_set, etc. 1 Notes: All operations provided by this module are callable by algorithms These operations are the only way to create critical sections within an algorithm and provide a processor independent way of controlling preemption. RTC_enable and RTC_disable take a mask that should be configurable; i.e., hard constants should not be used.

It is important to realize that none of the LOG, RTC, or STS operations has any semantic effect on the execution of an algorithm. In other words, it is possible to implement all of these operations as aliases to a function that simply returns and the operation of the algorithm will be unaffected.

Table 3 summarizes the C language run-time support library functions that may be referenced in an embodiment of the present invention.

TABLE 3 Run-Time Support Library Functions Allowed or Disallowed Category Typical functions in category Notes allowed String functions strcpy, strchr, etc. 1 allowed Memory-moving memcpy, memmove, memset, etc. 2 functions allowed Integer math support _divi, _divu, _remi, _remu, etc. 2 allowed Floating point support _addf, _subf, _mpyf, _divf, _addd, _subd 2.3 _mpyd, _divd, log10, cosh, etc. allowed Conversion functions atoi, ftoi, itof, etc. 2 disallowed Heap management malloc, free, realloc, alloc, etc. 5 functions disallowed I/O functions printf, open, read, write, etc. 4 disallowed Misc, non-reentrant printf, sprintf, ctime, etc. 5.6 functions Notes: Exceptions: strtok is not reentrant, and strdup allocates memory with malloc. The compiler issues some of these automatically for certain C operators. The errno paradigm isn't reentrant. Thus, errno must not be used. Algorithms are not allowed to perform I/O (except via DSP/BIOS APIs). Algorithms must not allocate memory. Algorithms must be reentrant and must, therefore, only reference reentrant functions.

All algorithms must follow certain programming rules: 1. All algorithms must follow the run-time conventions imposed by an implementation of the C programming language. 2. All algorithms must be reentrant within a preemptive environment (including time-sliced preemption). 3. All algorithm data references must be fully relocatable (subject to alignment requirements). That is, there must be no "hard coded" data memory locations. 4. All algorithm code must be fully relocatable. That is, there can be no "hard coded" program memory locations. 5. Algorithms must characterize their ROM-ability; i.e., state whether they may be placed in ROM or not. 6. Algorithms must never directly access any peripheral device. This includes but is not limited to on-chip DMAs, timers, I/O devices, and cache control registers.

The most basic software component is the module. In this embodiment, all algorithms are implemented as modules. A module is an implementation of one (or more) interfaces. An interface is simply a collection of related type definitions, functions, constants, and variables. In the C language, a header file typically specifies an interface. It is important to note that not all modules implement algorithms, but all algorithm implementations must be modules.

All modules must follow the following conventions:

Provide a single header that defines the entire interface to the module

Implement a module initialization and finalization method

Optionally manage one or more "instance" objects of a single type

Optionally declare a "Config" structure defining module-wide configuration options

For example, consider FIG. 3. Suppose a module called FIR, which consists of functions that create and apply finite impulse response filters to a data stream, is created. Interface 301 to this module is declared in the single C header file fir.h. Any application that wants to use the functions provided by implementation 302 in the FIR module must include the header fir.h. Although Interface 301 is declared as a C header file, the module may be implemented entirely in assembly language (or a mix of both C and assembly). Since interfaces may build atop other interfaces, all header files are required to allow for the possibility that they might be included more than once by a framework.

The general technique for insuring this behavior for C header files is illustrated in the code in Table 4.

TABLE 4 Sample Header File Code for Multiple Inclusion /* * ======== fir.h ======== */ #ifndef FIR.sub.-- #define FIR_ . . . #endif /* FIR */

A similar technique should be employed for assembly language headers, as illustrated in Table 5.

TABLE 5 Assembly Language Header ; ; ======== fir.h54 ======== ; .if ($isdefed("FIR_") = 0) FIR_ .set 1 . . . .endif

Since multiple algorithms and system control code are often integrated into a single executable, the only external identifiers defined by an algorithm implementation (i.e., symbols in the object code) should be those specified by the algorithm application program interface (API) definition. Unfortunately, due to limitations of traditional linkers, an identifier must sometimes have external scope even though it is not part of the algorithm API. Thus, to avoid namespace collisions, vendor selected names must not conflict. All external identifiers defined by a module's implementation must be prefixed by "<module>_<vendor>_<name>", where <module> is the name of the module (containing only alphanumeric characters), <vendor> is the name of the vendor (containing only alphanumeric characters), and <name> is the unique name of the identifier (containing only alphanumeric characters). For example, for a vendor "TI", TI's implementation of the FIR module must only contain external identifiers of the form FIR_TI_<name>. If there are external identifiers that are common to all implementations, the <vendor> component may be eliminated. For example, if the FIR module interface defined a constant structure that is used by all implementations, its name would have the form FIR_<name>.

In addition to the symbols defined by a module, the symbols referenced by all modules must be defined. All undefined references must refer either to the C run-time support library functions or to operations in the DSP operating system modules or to other modules that comply with the rules of this embodiment.

All modules must follow the naming conventions summarized in Table 6. Note that the naming conventions only apply to external identifiers. Internal names and existing code need not change unless an identifier is externally visible to a framework.

TABLE 6 Naming Conventions Convention Description Example Variables and functions Variables and functions begin with lower case (after LOG_printf() the prefix) Constants Constants are all uppercase G729_FRAMELEN Types Data types are in title case (after the prefix) LOG_Obj Structure fields Structure fields begin with lowercase Buffer Macros Macros follow the conventions of constants or LOG_getbuf() functions as appropriate

In addition to these conventions, multi-word identifiers should never use the `_` character to separate the words. To improve readability, use title case; for example, LOG_getBuffer ( ) should be used in lieu of LOG_get buffer ( ). This avoids ambiguity when parsing module and vendor prefixes.

Before a module can be used by an application, it must first be "initialized"; i.e., the module's init ( ) method must be run. Similarly, when an application terminates, any module that was initialized must be "finalized"; i.e., its exit ( ) method must be executed. Initialization methods are often used to initialize global data used by the module that, due to the limitations of the C language, cannot be statically initialized. Finalization methods are often used to perform run-time debug assertions. For example, a finalization method might check for objects that were created but never deleted. The finalization method of a non-debug version of a module is often the empty function.

Although some modules have no need for initialization or finalization, it is easier for frameworks to assume that all modules have them. Thus, frameworks can easily implement well-defined startup and shutdown sequences, for example.

Modules optionally manage instance objects. In this embodiment of the present invention, all algorithm modules manage instance objects. Objects simply encapsulate the persistent state that is manipulated by the other functions (or methods) provided by the module.

A module manages only one type of object. Thus, a module that manages objects roughly corresponds to a C++ class that follows a standard naming convention for its configuration parameters, interface header, and all external identifiers.

FIG. 4 illustrates this concept. Object 401 is created by function 402 of module 403. Module 403 implements a finite impulse response filter.

Many embedded systems are very static in nature. Memory, MIPS (millions of instructions per second), and I/O peripherals are statically partitioned among a fixed set of functions that operate continuously until power is removed. Static systems permit a number of performance optimizations that simply are not possible in dynamic systems. For example, a memory manager is not required in a static system and general data structures, such as linked lists, can often be replaced with much simpler and more efficient structures, such as fixed length arrays. These optimizations obviously reduce the system's code size requirements and, they may have a significant effect on the execution performance of the system.

When designing a system that is very cost sensitive, must operate with limited power, and/or has limited MIPS, designers look for portions of the system that can be fixed at design time (i.e., made static). Even if the entire system cannot be static, often certain sub-systems can be fixed at design time. It is important, therefore, that all modules efficiently support static system designs. In practice, this simply means that all functions that are only required for run-time object creation be placed either in separate compilation units or separate COFF (Common Object File Format) output sections that can be manipulated by the linker. Ideally, every function should be in a separate compilation unit so the system integrator can eliminate run-time support that is unnecessary for a static system. An example that illustrates this "design-time" object creation for static systems is presented later in this specification.

Modules may optionally support run-time object creation and deletion. In some applications, run-time creation and deletion is a requirement. Without the ability to remove unneeded objects and reuse memory, the physical constraints of the system make it impossible to create rich multi-functions applications.

Run-time creation of objects is valuable even in systems that do not support or require run-time deletion of these objects. The precise nature of the objects, the number of objects, and even the type of objects created may be a function of parameters that are only available at run-time. For example, a programmer may want to create a single program that works in a variety of hardware platforms that differ in the amount of memory available and the amount is determinable at run-time. Note that the algorithms conforming to an embodiment of the present invention are modules of a special type, which are referred to as algorithm modules herein. How the algorithm modules support run-time object creation is another embodiment of the present invention described later in this specification.

In an ideal world, a module that implements an API can be used in any system that requires the API. As a practical matter, however, every module implementation must make trade-offs among a variety of performance metrics such as program size, data size, MIPS, and a variety of application specific metrics such as recognition accuracy, perceived audio quality, and throughput. Thus, a single implementation of an API is unlikely to make the right set of tradeoffs for all applications.

Therefore, any framework that wishes to incorporate modules following the specification herein must support multiple implementations of the same API. In addition, each module has one or more "global configuration" parameters that can be set at design time by the system integrator to adjust the behavior of the module to be optimal for its execution environment.

Suppose, for example, that a module that implements digital filters exists. There are several special cases for digital filters that have significant performance differences such as all-pole, all-zero, and pole-zero filters. Moreover, for certain DSP architectures if one assumes that the filter's data buffers are aligned on certain boundaries, the implementation can take advantage of special data addressing modes and significantly reduce the time required to complete the computation. A filter module may include a global configuration parameter that specifies that the system will only use all-zero filters with aligned data. By making this a design-time global configuration parameter, systems that are willing to accept constraints in their use of the API are rewarded by faster operation of the module that implements the API.

Modules that have one or more "global" configuration parameters should group them together in a C structure, called XYZ_Config, and declare this structure in the module's header. In addition, the module should declare a static constant structure named XYZ of type XYZ_Config that contain the module's current configuration parameters.

FIG. 5 contains the code for a very simple module to illustrate the concept of modules and how they might be implemented in the C language. This module implements a simple FIR filter.

As discussed above, the first two operations that must be supported by all modules are the init ( ) and exit ( ) functions. The init ( ) function is called during syst