Interactive C-code cleaning tool supports multiprocessor SoC design - Embedded.com

Interactive C-code cleaning tool supports multiprocessor SoC design

Multiprocessor system-on-chip (MPSoC) platforms have recently raised the industry's expectations as they promise to meet the high-performance targets for multimode multimedia terminals without giving up the requested flexibility.

However, writing software for MPSoC platforms is not straightforward. Designers are used to writing sequential applications in C code and optimizing these applications for embedded platforms. But transforming these sequential programs into functionally equivalent (in other words, correct ) parallel programs is a time-consuming and error-prone job.

The C language provides much expressiveness to specify what a program must do, but it's this expressiveness that makes C programs hard to analyze and transform. What's more, customers want these parallel programs to perform at optimal levels while efficiently using MPSoC platform's resources, such as power consumption and bandwidth usage.

The realities of source code and parallelization
It's an illusion to think we can take any piece of sequential code and hope that we can transform this code into an efficient parallel version, just like that. In fact, heavily optimized sequential code bases are often not the most appropriate candidates to start with in the first place. And to make matters worse, we want to explore different types of parallelizations quickly and easily, without rewriting significant parts of the program over and over again. Tools can help us in transforming the source code, but in the end, there is no silver bullet: either the designer or the tool (or both) must sufficiently “understand” the source code to be able to transform it correctly and efficiently. Hence, it's crucial that we identify those constructs in the source code that hamper this process. These can be code constructs at the level of programming language idioms or even at the level of design patterns for parallel programming. Once we've identified these constructs, we may elaborate rules that specify in which circumstances these constructs should be avoided.

This is the rationale of IMEC's so-called CleanC rules that have been elaborated during the development of an MPSoC application-mapping tool suite. These rules target ANSI-C language idioms that make the process of mapping sequential C programs onto an MPSoC platform more difficult. They consist of a few tens of guidelines and restrictions. Code restrictions are constructs that aren't allowed to be present in the input C code for the tools to work (on that part of the code).

For instance, undisciplined use of preprocessing information in C can make life very hard for any kind of source-code transformation tool. Code guidelines describe how code should be written to give the tools maximum accuracy and transformation freedom. The majority of these rules transcends the specific functionality of the IMEC mapping tools and may form the basis for a standard set of guidelines for programming MPSoC platforms in a “clean” code called CleanC.

How CleanC differs from C
We can roughly classify the CleanC rules in four different groups. These classifications are not completely independent. For instance, applying a rule from one category may strengthen the effects of rules in other categories.

Category 1–Rules to enable and improve source-code transformations. The IMEC mapping tools are source-code transformation tools. One of the design goals of these tools was the ability to retain the structure of the original source code as much as possible when performing transformations. This makes the transformed code easier to recognize and understand, which is useful when the designer must edit the transformed code.

Undisciplined use of header files and C preprocessor statements makes this design goal difficult to achieve. A subset of CleanC rules detail how to properly use header files and preprocessor statements. Source-code transformations may also introduce conflicts between variable names; hence, CleanC suggests using different names for different things. Other constructs that make source code transformations more difficult include irregular control flow and expressions with side effects.

Category 2–Rules to enable and improve data-dependency analysis. A major challenge in parallelizing code and optimizing usage of the memory hierarchy consists of dealing with data dependencies. Knowing which data are needed by which parts of the code and understanding the exact dependencies between the program parts that update the data and the parts that read those data are crucial instruments for parallelizing and optimizing the code. Brute-force approaches for synchronizing accesses to shared data resources may result in worst-case assumptions about the programs behavior. Hence they are typically bound to be suboptimal at best and highly inefficient at worst. Thus, we must be able to analyze data dependencies in more precise and fine-grained ways: for instance, which parts of a video frame may be safely processed in parallel by a video encoder application.

To achieve this goal, a subset of the CleanC rules detail how to use constructs that reveal the intention of the designer more clearly. For instance, when processing a video frame, it's easier to analyze the code when the designer uses an explicit code construct to represent the frame as a two-dimensional array with explicit indexing to access the pixel values, and when the designer uses canonical for loops with known bounds to enumerate the pixels. (The IMEC mapping tools understand a controlled form of dynamic multidimensional memory allocation.) Equivalent code with data and function pointers and with pointer arithmetic often obscures the intentions and makes the analysis more difficult.

Some exceptions to this intention-revealing principle exist, however. For instance, while recursive function definitions often express the intention more clearly than their nonrecursive counterparts, they are typically harder to analyze by tools.

Category 3–Rules to minimize data dependencies. Needless data dependencies complicate the analysis process and may lower the quality of the analysis results. This, in turn, affects the ability to optimize and parallelize the source code. CleanC not only details to avoid global variables and duplicated functionality, but it also imposes stricter constraints on the usage of types: types with different names are basically considered different.

Using code constructs like global variables also has more direct negative effects, for instance by needlessly increasing the lifecycle of large data structures.

Category 4–Rules to avoid the dark corners of the C standards. The C standards contain many elements that not defined or, in general, not well understood. The CleanC rules specify a limited set of constructs that should be avoided. More rules of this type can be found elsewhere, such as in the Misra C guidelines available at www.misra.org.uk.

Putting CleanC to work
Rather than exhaustively delineate these and other categories of rules for writing C-code for multiprocessor designs, following are examples of some of these rules at work.

Example #1–Guideline: use the manifest loop pattern. Many optimizations rely on analyzing exactly which data element is accessed at which point in time. That requires interpreting how index expressions evolve over the execution of the loops. Therefore, it must be possible to interpret the index expressions, the loop bounds, and how the loop iterator is incremented. To make this interpretation easier, CleanC uses a fixed pattern for manifest loops. A manifest loop is executed in exactly the same way, independent of the input received by the code. More formally, a manifest loop is a loop with an iterator that is initialized with a manifest value. The iterator is incremented or decremented with a constant value in each iteration, and the loop finishes when the iterator reaches a certain manifest value. A manifest value is a value that is either constant or computed from the iterators of outer loops. Nonmanifest loops, on the other hand, have no restriction on how they should be written.

In CleanC, only loops that follow this fixed pattern are recognized as being manifest by the tools. Therefore, it mostly is just a matter of using the pattern instead of using, for example, a while loop. If the iterator is updated in several places, this can usually be replaced by a fixed update and not executing the loop body in some iterations.

A loop with a data-dependent upper bound (the typical while loop) can be replaced by a manifest loop over the maximum number of iterations with a condition nested inside it. However, this is only useful if the iterator is then used in some index expression.

Here is an example where the guideline is followed:

for (i=0; i < 100; i = i + 4)     for (j=i; j < 150; j++)        if (j%5 != 0)           ...   

and a counterexample (in other words, where the guideline is not followed):

i=0;while (i<100) {     for (j=i; j<150; j++) {        ...        if (j%5 == 0)                j++;     }     i = i + 4;}   

Figure 1 shows a screenshot of an example of the guideline “manifest loop pattern” violation as it would appear in the CleanC tool.

View the full-size image

Example #2–Restriction: distinguish source files from header files.

The C language does not formally distinguish between the interface and the implementation of a module. It only provides the #include preprocessor directives, which can be used to separate interface from implementation but which can also be abused for many other things. The textual replacement of preprocessing directives is however hard to interpret by humans and is almost impossible to reconstruct by transformation tools.

Transformation tools will therefore expand preprocessing directives unless they follow a particular pattern. The most occurring pattern for #include is to refer to header files that contain declarations. This pattern is therefore supported. The tools keep track of the file in which a variable or function is defined or declared. The problem pops up when the same file is included in several other files: any definition in that file will create several separate instances of the variable or function. The tools don't keep track of these separate instances. They, therefore, disallow definitions in header files.

In CleanC, two types of files exist. Source files contain definitions of functions and variables, in other words, the implementation of a module. A source file can contain #include directives to header files. A header file contains only declarations of functions, variables and types, no definitions. A header file can also #include other header files. Any other use of the #include directive leads to confusion. An exception to this rule is the definition of an inline function: that definition must be in the header file; otherwise, it's not possible to inline the function at the place where it is called. Header files should have the file extension .h . Source files should have the file extension .c .

Hence, any use of the #include directive that doesn't conform to this pattern should be expanded. Declarations should be moved to a header file that is #include'd in the source files calling the function or accessing the variable.

For an example and counterexample, see Listings 1 and 2 .

View the full-size image

View the full-size image

Example #3–Guideline: keep variables local. Variables in C can be declared local to their surrounding block, or they can be declared global (by using the “extern” keyword or by declaring it outside of a function). In CleanC, global variables should not be used. The problem with using global variables is that accesses to global variables aren't explicitly visible in function calls.

This problem makes understanding of the dependencies between function calls and other expressions very hard. Tools can't assure us that global variables aren't being accessed by functions (such as library functions) whose definitions the tools can't see. A call to such a function makes all global variables “call clobbered.”

That means that the function is assumed to read and write all global variables, thereby introducing many unnecessary dependencies. This may unnecessarily block transformations. Instead, in CleanC, the variable should be declared locally and passed as a parameter to other functions using it. A code-cleaning transformation tool can move a global variable to a function scope and add parameters to other functions and their calls as required. Listings 3 and 4 show an example and counterexample relating to a practical implementation of CleanC.

View the full-size image

View the full-size image

CleanC's analysis tools
IMEC introduces the CleanC analysis tools to assist designers in analyzing the source code and identifying the problematic constructs. For example, with respect to usage of the manifest-loop pattern, optimization tools indicate which loops do not follow this pattern. As a result, violations of the CleanC rules are listed.

The analysis tools also include various visualizations of function-call graphs, as some types of CleanC violations are easier to convey in a graphical way. User-guided code transformations may then be applied to the source code to make it compliant with the CleanC programming style. To optimize this process, IMEC is currently developing interactive refactoring tools. For example, to distinguish source files from header files, a code-cleaning transformation tool may automatically expand any preprocessing pattern that is not supported by the optimization tools.

The analysis and refactoring tools are available as plug-ins for the Eclipse/CDT (C/C++) development platform. These tools are thus integrated in a highly interactive environment where the code may be checked or transformed at any moment while it's being developed and tested.

Figure 2 shows a visualization of the function call graph, showing functions as boxes and function calls as arrows.

Once the code has been cleaned into CleanC compliant code, it can be used as source code for IMEC's mapping tools that assist the designer in mapping the application onto the parallel platform. These tools are responsible for exploring the mapping solution space and for efficiently mapping the CleanC sequential algorithm onto the parallel platform-programming model. The multiprocessor parallelization assist (MPA) tool automatically transforms C source code into parallel source code based on designer directives. The tool supports both data-level parallelism and pipeline parallelism, two basic parallel programming patterns. The tool also recognizes and optimizes certain forms of divide-and-conquer parallelism: here a sequential task can be split in parallel tasks, but the results of these tasks must be processed by an associative function (like addition or multiplication).

The memory hierarchy (MH) tool optimizes usage of the memory hierarchy by sequential C programs. It can autonomously introduce data copies, map them onto scratchpad memories, and insert the necessary direct-memory-access transfer instructions based on a combination of static analysis and profiling information.

Both the MPA and MH tools derive their strengths from the ability to analyze relevant data and control-flow dependencies in the complete input program.

The CleanC tool suite, the MPSoC mapping tools together with predictable platform services constitute IMEC's global approach to MPSoC application mapping. Figure 3 shows the MPSoC programming model.

Costs and benefits of code cleaning

View the full-size image

The rationale behind IMEC's MPSoC mapping flow is that designers should preferably program at the sequential level and perform the parallelization afterwards. This means that the source code must be cleaned. The question arises then, what is the cost of code cleaning?

In one scenario, the designer develops the source code from scratch. In this case it suffices to follow the cleaning guidelines and to run the CleanC analysis tools on a regular basis. Here, there is little or no overhead in cleaning the code.

In case the source code already exists, designers may object at the cost of cleaning the source code first. However, given CleanC code in combination with IMEC's MPSoC mapping tools, it becomes much easier to explore even very different correct-by-construction parallelizations in a short time. An experienced designer can explore the trade-offs of, say, 10 different nontrivial parallelizations of an MPEG4 encoder in a day. The advantages offered by this fast exploration and optimization process then outweigh the cost of cleaning.

We have found that the application cleaning and mapping tools eventually contribute toward a decreased time to market, with a lower risk (both in time and performance) when mapping and integrating software applications components and hardware/ software services on top of an MPSoC platform.

Mieke Van Bavel is scientific editor at IMEC, the Interuniversity Microelectronics Center (EC) in Leuven, Belgium. She may be reached at mieke.vanbavel@imec.be.

At IMEC in Belgium, Michael Tilman leads the software engineering team within the Nomadic Embedded Systems division. He is responsible for the development of tools that assist designers in cleaning and mapping sequential code onto heterogeneous multiprocessor platforms. He may be reached at michel.tilman@imec.be.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.