Allocating memory in MATLAB-to-C code
When developing algorithms for communication, signal processing, and controls, MATLAB is the de facto standard development environment. MATLAB's syntax and toolbox functions greatly facilitate algorithm exploration and refinement.
At some point, however, a MATLAB algorithm must be ported to another implementation, typically C. Embedded systems, in which many algorithms eventually end up as software, can impose additional requirements on memory usage. In this article, we'll look at how data storage in MATLAB translates to memory allocation in C for embedded systems.
Translating MATLAB code to C is not a straightforward process. Translation techniques have already been discussed in a series of articles republished on Embedded.com (www.embedded.com/204301366), and tools now exist for automatic MATLAB-to-C translation. In embedded software, one of the biggest concerns is memory usage. This topic has been covered extensively by Niall Murphy ("Safe Memory Utilization," April 2000, www.embedded.com/2000/0004/0004feat2.htm), but we can summarize some of the pertinent points about embedded memory usage relevant to MATLAB.
In C, the developer has the choice of allocating memory either on the stack, in static memory, or dynamically (on the heap). Each allocation method has its advantages and disadvantages.
Static allocation, in which the compiler sets aside a fixed amount for each variable, is the simplest method and works even on processors without stack support. However, this method inefficiently allocates all storage memory for the lifetime of the program, so more memory is allocated than is actually in use. In addition, the amount of memory is fixed and must be specified at compile time. For example in Listing 1, the memory for variable "array" is allocated statically.
In stack allocation, the processor allocates a fixed amount of memory when a function is invoked. The memory for the currently executing function is maintained on a stack, and when the function exits, the memory on the stack is released. This method uses memory more efficiently than static allocation, because memory is allocated and released as needed by each function. However, the stack is limited to a finite area of memory. It can be difficult to predict how large the overall stack needs to be, and stack overflow can be difficult to detect. Like static allocation, the size of variables on the stack must be specified at compile time. Listing 2 illustrates stack allocation for variable "array."
Finally, in dynamic allocation, you manually allocate memory at run time. The memory is drawn from the heap, using C's malloc and free commands. Because you have complete control over memory usage, dynamic allocation allows more efficient use of memory than either static or stack allocation. Listing 3 shows an example of dynamic allocation.
The flexibility of dynamic memory allocation, however, comes at a price:
• Manual memory management is error prone, and heap-related software problems, such as memory leaks, are particularly difficult to debug.
• Searching the heap for an appropriate size block takes an indeterminate amount of time, which is unacceptable for "hard" real-time systems.
• Repeatedly allocating and freeing memory blocks of different sizes eventually leads to fragmentation.
• Custom memory allocators, such as memory pool managers, avoid these problems, but introduce more complexity and possible defects into the system.
Given these issues, embedded software developers traditionally frown upon dynamic memory allocation, especially in software for mission-critical systems and avionics. Many embedded software projects forbid the use of dynamic memory allocation entirely.
In MATLAB, you don't need to think about memory allocation. The MATLAB interpreter handles details of array memory and data types, leaving the algorithm developer free to concentrate on the algorithm itself. In fact, typical MATLAB users don't even worry about array sizes, as MATLAB will automatically resize arrays as required. For this article, however, we'll identify two types of MATLAB arrays: fixed-size arrays and variable-size arrays. Fixed-size arrays are MATLAB arrays for which the dimensions remain fixed during run time. Variable-size arrays change in size or shape during run time. Some MATLAB examples are shown in Listing 4.
Variable-size arrays are an extremely useful feature of MATLAB, and most non-trivial MATLAB programs make use of them; sometimes you simply don't know how large an array (such as an image or resampled buffer) will be until run time. Although the MATLAB language doesn't explicitly distinguish between fixed-size arrays and variable-size arrays, you'll see that this distinction becomes critical when translating to C.
Embedded C for fixed-size arrays
When translating MATLAB code to C, you must choose how to allocate memory for your data. If the MATLAB code uses a fixed-size array, where the array size doesn't change during run time, the translation is a simple matter of allocating an equivalent array in C. Because the array size is known at compile time, you can allocate the array statically or on the stack, and there's no need to resort to dynamic allocation.
For example, the MATLAB function in Listing 5 maps one integer to another via a simple look-up table (LUT), which is a vector of fixed size.
The equivalent C code, with LUT allocated on the stack, is shown in Listing 6. Similarly, you can allocate LUT in static memory, as shown in Listing .
A tool we developed for MATLAB-to-C translation takes the same approach to fixed-size arrays. When the size of a MATLAB array is known ahead of time, it simply allocates the equivalent array in C. By default, the translation tool uses the size of the array to determine whether to allocate the array on the stack, statically, or dynamically. However, you have complete control over this behavior, and, for example, can direct the translator to avoid all dynamic memory allocation.
Embedded C for variable-size arrays
If your MATLAB code uses variable-size arrays, how do you translate them to C? The natural solution is to allocate an equivalent array dynamically, but in an environment that prohibits dynamic memory allocation, you have several solutions for handling the variable-size array:
• Rewrite the algorithm to eliminate all variable-size arrays: you can emulate variable-size arrays by pre-allocating a maximum, fixed-size array, then use extra "bookkeeping" variables and logic to track the actual array size during runtime. This method can be done in C or even MATLAB, although this goes against the grain of normal MATLAB coding style.
• Use a custom memory allocator in C, such as a pool manager, to allow dynamic memory allocation without the associated problems: this solution sidesteps the problems with malloc and free but introduces extra complexity.
As an example of variable-size arrays in MATLAB, consider the MATLAB find function: given a vector x, the MATLAB statement "ind=find(x)" returns a vector ind of indices corresponding to non-zero entries of x. The exact length of ind cannot be determined until run time. Find is a commonly used function in MATLAB, but the variable length of the output makes translation to C problematic, especially when dynamic memory allocation is prohibited.
The example in Listing 8 initializes x with ten random numbers between 0 and 1.0, then returns the indices of elements in x that are greater than 0.5. The length of ind isn't known until after the random numbers are generated.
To avoid dynamic memory allocation, you can recognize that the length of ind will never exceed the length of x (=10). This gives you the maximum possible size for ind, which you allocate on the stack. You can also introduce a separate variable, ind_dim1, to track the actual size of ind. The resulting C translation of findrand is shown in Listing 9.
MATLAB might set you free
The MATLAB language frees you from having to think about memory allocation and actively encourages the use of variable-size arrays. On the other hand, many algorithms developed in MATLAB are eventually ported to C on an embedded system, where memory, time, and hardware constraints limit how the C implementation allocates memory. In some cases, embedded projects prohibit the use of dynamic memory allocation entirely. It's no wonder that translating from MATLAB to embedded C is a complicated task.
Robert Yu is an applications engineer at Agility Design Solutions involved in the development and use of the company's Agility MCS product for automatic MATLAB-to-C translation tool in embedded applications. Before joining Agility, he held software development and management positions at a variety of Silicon Valley companies. During this time, his work focused on signal processing and telecommunications applications. Robert holds BS and MEng in electrical engineering from Cornell. He can be reached at firstname.lastname@example.org.