Multicore processors are a game changer. We need look no further than our smartphones to see the impact of their remarkable processing power. Before multicore, processor performance doubled each year. As semiconductor technology advanced, the number of transistors on a chip grew from a million in 1990 to more than a billion today. As the limits of miniaturization were approached, the industry turned to multicore designs to sustain the pace of improved performance, so now quad-core processors are commonplace. The ability to multiply processing power through parallel processor cores enables extraordinary performance.

Concurrency is not a new topic, but it takes on a new dimension in multicore platforms. Software developers have been accustomed to think of concurrency in terms of task scheduling and context switching within a single processor. However, with multiple processor cores, true parallelism comes into play: the streams of instructions in each thread are being executed in parallel on each core. Communication between threads is often achieved using shared memory, and synchronization of access to this shared resource is often the biggest source of complexity and if done incorrectly, a major cause of bugs (Figure 1).

Writing a correct concurrent program is notoriously difficult, and multicore architectures make it significantly harder. With their added complexity, multicore platforms exacerbate the effect of concurrency bugs, making them particularly pernicious. These bugs, which include race conditions, deadlocks, livelocks, and resource starvation, are difficult to find when they manifest and even more difficult to diagnose[1]. Programs that run error-free on a single processor can exhibit latent bugs such as deadlocking on a multicore system (Figure 2). Concurrency bugs can present unusual symptoms that surface long after the initial events that triggered them and are frequently hard to reproduce. Because such bugs can be very difficult to find during testing, multicore systems require a new approach to verification that specifically addresses concurrency errors. By far, the most effective way to reduce the risk of these bugs is to take a multifaceted approach that includes peer code reviews, testing, and, most of all, advanced static analysis that incorporates sophisticated models for concurrency.

Programming language support

Unlocking the full performance potential of a multicore system requires advanced programming techniques. Since most embedded developers are relatively new to multicore programming, the risk of introducing concurrency bugs is very significant. Today, C and C++ are still the most popular programming languages for embedded systems. However, one of the fundamental weaknesses of these languages is that they were not designed for concurrency. The most recent versions, C11 and C++11, introduced standardized support for multi-threading. Three features were added to address concurrency: a memory model that defines the behavior of multi-threaded programs; atomic data types that can be safely accessed by concurrent threads; and several synchronization primitives such as locks and condition variables. Notwithstanding these improvements, the languages retain many of the core features of their ancestors that make writing multi-threaded programs very hazardous.

At the same time, Java is increasingly popular with embedded developers, and with 28 percent using it today it is now the third most popular language for embedded systems. In contrast to C and C++, Java has always had built-in support for multithreading within the programming language syntax, source compilers, and standard libraries. Additionally, Java 5 added the java.util.concurrent library, which was extended in Java 6 and Java 7 to provide extensive support for concurrent and parallel programming.

Many embedded designs use a combination of C or C++ and Java. For example, Java is very popular for automotive applications because it offers an easy way to program a user interface for a touchscreen display or an entertainment system. Such applications may have many layers with safety-critical code written in C, communicating with non-safety-critical Java code running on a user interface.

Static analysis tools

Perhaps the biggest challenge with concurrent programs for multicore platforms is that no amount of testing can be guaranteed to find all concurrency bugs. It is the relative order in which instructions are executed in real-time that is the main source of defects in multi-threaded programs. As multiple threads run, the relative order in which their instructions are executed varies depending on what other threads are active at the same time. If bugs are introduced through programming errors, non-determinisitic interleaving can lead to unpredictable results. The number of possible interleavings increases enormously as the number of instructions grows, a phenomenon known as combinatorial explosion. Even the smallest threads have many possible interleavings. Real world concurrent programs have astronomical numbers of legal interleavings, so testing every interleaving is unfeasible. Likewise, it is impossible to explore every potential execution path using peer code reviews or walkthroughs. This is where advanced static analysis tools excel.

Advanced static analysis tools use symbolic execution engines to identify potential problems in a program without actually having to run the program. They work much like compilers, taking source code as input, then parsing it and converting it to an Intermediate Representation (IR). Whereas a compiler would use the IR to generate object code, static analysis tools retain the IR, also called the model. Checkers perform analysis on the code to find common defects, violation of policies, etc., by traversing or querying the model, looking for particular properties or patterns that indicate defects. Sophisticated symbolic execution techniques explore paths through a control-flow graph, which is a data structure representing the order in which statements are executed in a program. Algorithms keep track of the abstract state of the program and know how to use that state to exclude consideration of unfeasible paths. The depth of the model determines the effectiveness of the tool. That depth is based on how much knowledge of program behavior is built in, how much of the program it can take into account at once, and how accurately it reflects actual program behavior.

Many developers take advantage of popular open source tools to find bugs in Java, including FindBugs, PMD, and CheckStyle. The most widely used of these, FindBugs, uses static analysis to identify hundreds of different types of potential errors in Java programs. FindBugs operates on Java bytecode, the form of instructions that the Java virtual machine executes. PMD and CheckStyle check source code for adherence to coding standards and detect bad practices.

Each of these tools has its strengths. An important advantage of static analysis tools, in general, is that they can be used early in development to find bugs even before testing begins. Most of the static analysis tools available for Java are general purpose and catch a range of surface level problems.

In comparison to these open source tools, there are commercial products that are tailored for very precise identification of concurrency problems in Java, C, or C++. These tools incorporate very deep models that enable them to find concurrency problems that are often missed by other tools. Some of the most effective of these advanced static analysis tools are based on cutting-edge academic research into software concurrency behavior. They offer advanced static analysis of C and C++ source code with whole program interprocedural analysis and can typically handle programs with up to 10 million lines of code. In addition to finding race conditions and deadlocks, one of the commercial tools for Java identifies unpredictable results caused by incorrect use of the concurrent collection libraries provided by java.util.concurrent. It detects bad error handling or incorrect synchronization when coordinating access to shared non-concurrent collections. Also, it can help diagnose performance bottlenecks caused by incorrect API usage, redundant synchronization, and unnecessary use of a shared mutable state (Figure 3).

Since many projects will include Java and C or C++, teams will find it easier and more productive to work with tools in an Integrated Development Environment (IDE). There are tool suites that can be used for both embedded and hosted platforms. Commercial versions offer automated work flow and powerful tools for program analysis, program inspection, program understanding, and architecture visualization. Using an IDE with targeted advanced static analysis tools enables developers to discover the underlying design intentions of existing concurrent code, and recognize when new code deviates from this design. It provides early warning when new concurrency defects are first introduced and uses cutting-edge technologies to help developers identify and understand them.

Effective multicore system design

Developing embedded applications for multicore platforms requires a new approach. Advanced programming techniques are needed to take advantage of the parallel processing cores. The interleaving of program threads across the parallel processors creates an astronomical number of potential execution paths. This makes it impossible to test or review every possible scenario. Static analysis offers the only feasible means to explore all possible code paths for software errors in highly concurrent systems. When used in conjunction with other code quality practices such as code reviews and integration testing, advanced static analysis tools can significantly reduce the risk of field failures due to undiscovered concurrency bugs.

References

[1] "Conquering Complex Java Concurrency Bugs with CodeSonar." GrammaTech. N.p., n.d. Web. 19 May 2014. <http://www.grammatech.com/resources/whitepapers>.

Paul Anderson is Vice President of Engineering at GrammaTech. Dr. Anderson received his B.Sc. from Kings College, University of London and his Ph.D. from City University London. Dr. Anderson’s work has been reported in numerous articles, journal publications, book chapters, and international conferences.

GrammaTech www.grammatech.com @GrammaTech opsy.st/GrammaTech_Linkedin opsy.st/GrammaTechGooglePlus opsy.st/GrammaTechYouTube www.grammatech.com/blog