Design Feature: July 18, 1996

Once the domain of supercomputers and research laboratories, multiprocessing is becoming a mainstream computer architecture. Off-the-shelf multiprocessor operating systems (OSs) and hardware have made software development easier, but not simple. Structuring software to take advantage of multiprocessing and debugging system code still present difficulties for designers.

The movement toward mainstream use of multiprocessing began with the introduction of multitasking OSs, such as Posix and Windows 95. Multitasking places many of the same constraints on software as does multiprocessing, including the need for processes to share system resources before completing their tasks. Multitasking OSs have structures in place to allow resource sharing.

The increased use of DSPs has also pushed multiprocessing toward the mainstream. DSPs often operate in specialized multiprocessing configurations, such as pipelines. Most DSPs have hardware structures that simplify interprocessor communications for data sharing. Even the PC is moving toward multiprocessing. The Pentium Pro processor has a dedicated bus that allows four processors to share the PC's resources and execute multiple tasks simultaneously.

As designers approach multiprocessing for the first time, there are many software-design options available to them. The simplest form of multiprocessing software places independent programs on each of the multiple CPUs, with some communication between programs. Designers can create and debug such systems one processor at a time using conventional methods. These systems don't readily scale to adding processors, however, or adapt to changes in the interconnect structure.

Another form of multiprocessing software available to designers is distributed cooperating tasks. Distributed and microkernel OSs (References 1 and 2) allow designs to map to a variety of hardware structures. Further, the mapping is table-driven and easy to modify, allowing the software to adapt to new hardware configurations with a simple recompilation.

Using the most general form of multiprocessing software, the multiple processors share the same task. The software structure for this objective depends on the hardware configuration in use, and the system memory's structure is a critical consideration.

Three sisters of memory

System-memory structures for multiprocessing designs include unified memory-access (UMA), nonuniform memory access (NUMA), and no read/write memory access (NORMA). UMA allows all processors equal access to system memory. Such designs are also called "symmetric-multiprocessing" or "tightly coupled" systems. Workstations and Pentium Pro systems use this architecture.

UMA structures allow the fastest possible interaction between processors. Those systems don't scale indefinitely, however, because ensuring memory access becomes more difficult as you add processors. The software overhead for controlling memory access begins to supersede performance gains when you use more than eight to 10 processors.

NUMA allows processors private memory in addition to sharing a portion of system memory. And, access times for the two memory types do not have to be identical. VME systems can use this architecture, in which each processor board has local memory, as well as access across the backplane to shared memory.

Fully distributed systems have NORMA structures. Processors in those systems have no access to common memory. Instead, all data sharing must occur over communications links.

Within each of these memory structures, there are several possible program-processing possibilities for the program's processing structure. Activities that process large data arrays, for example, can use a single-instruction, multiple-data (SIMD) approach. Such programs partition large data arrays into subarrays; then, each processor performs the same processing steps on its own subarray. Image-processing activities, such as a discrete cosine transform or search operations on a database are tasks amenable to the SIMD approach. Programming an SIMD system is relatively easy, because each processor runs essentially the same program.

The data-flow model is another straightforward multiprocessing-program structure. With this structure, processors perform an operation on streams of data coming from other processors and then pass the results on to other processors. Processors have a fixed function and interact with each other only if the data flow passes between them, so programming remains uncomplicated. The pipeline-processing algorithms common in DSP applications are one type of data flow. Data-flow systems can employ feedback loops and have multiple sources and destinations at each stage.

When your tasks or data are not suited to one of these simpler multiprocessing forms, however, software design quickly becomes complex. Designers programming a multiprocessing system to accelerate general computing operations face challenges. Many of these challenges relate to accessing common resources, such as data.

If two or more processors run programs that manipulate the same block of data, the system needs a protection scheme that coordinates the use of that data. For example, the two processors may attempt concurrent read-modify-write operations on a block of data. Both read the same value but make different modifications. The processor that finishes last unknowingly overwrites the changes that the first processor made. If the processors have local cache memory, the possibility of overwriting becomes even greater. Unless the system recognizes that one processor's operations have invalidated the cache on another processor, corrupt data quickly propagates throughout the program.

Caches aside, having the first processor place a lock on the resource while making its modifications prevents some overwriting but introduces the possibility of deadlocks. In a deadlock, the first processor locks resource A but needs resource B to complete its task. The second processor locks B but needs A. The two processors become deadlocked, waiting for each other to release the held resources.

Fortunately, many off-the-shelf OSs have built-in tools for resolving these and other multiple-access problems. Distributed OSs (Reference 1), for example, are designed to handle multiple-system-resource requests in a multiprocessing environment. The Ada programming language and associated OSs also incorporate multiprocessing as a baseline configuration. More traditional uniprocessor OSs, such as Integrated Systems' pSOS, Lynx Real Time Systems' Lynx OS, and Wind River Systems' VxWorks, have added extensions to handle multiprocessing needs. DSP OSs, such as Multiprocessor Toolsmiths' Unison and Spectron Microsystems' Spox-MP, solve many of the access problems associated with shared-memory multiprocessor configurations.

Many of these OSs allow designers to develop their code as though it operates on a single processor. The OS can then automatically distribute the code's elements across the various processors in the system. In some cases, the OS can also automatically select among parallel interprocessor-communications links, thus improving system reliability.

Careful code structure needed

The result of these OS capabilities is that software design for multiprocessing systems has become much easier. The OS handles most of the difficulties inherent in multiprocessing, freeing the designer to focus on the application's needs, not the implementation details. It would be a mistake, however, to believe that the OSs make multiprocessing automatic. Designers still need to structure their code to make multiprocessing effective.

One of the first things designers must consider is the distribution of software tasks among the processors. Many OSs can automatically make such distributions, but designers obtain better results by directing task distribution. The rule of thumb is to place tasks where they make sense.

Tasks that need specific hardware resources, for example, run best on the processor that has direct access to those resources. Although the OS may allow an output-data-formatting task to run in one processor while another processor handles the I/O task, the system may run faster if the same processor handles both tasks, eliminating interprocessor-communications overhead. Similarly, two tasks that need a high-bandwidth link between them may benefit from running on the same processor. Tasks that don't intercommunicate are good candidates for scattering among several processors.

In addition to task assignment, designers must consider the order of task execution. In single-processor systems, software tasks execute sequentially, except for interrupts. Task A begins before task B begins. Multiprocessor systems destroy such sequencing. Tasks may execute simultaneously or randomly. Designers must allow for this random ordering, ensuring either that tasks have no temporal dependencies or that tasks wait for their proper place in the sequence.

Forcing the code to follow a set task sequence, however, may result in software that gains nothing from a multiprocessing environment. A two-processor system in which each processor is 50% idle offers no performance advantage over a fully utilized single processor. A multiprocessor system could even slow fixed-sequence software. The overhead associated with controlling shared-resource access delays task execution, and the fixed sequence prevents the multiprocessing configuration from providing any performance gains.

Debugging: a formidable task

By keeping task assignment and sequencing in mind during design, software developers can effectively use multiprocessing OSs. But, design is only half the task in software development. The other half is debugging. Debugging in a multiprocessing environment can be a formidable task.

One of the first things designers should realize is that debugging multiprocessing software involves finding both logical errors in the code and errors in the interaction between parts of the code. A useful approach to multiprocessing debugging is to debug the code's logic in a uniprocessor environment. Standard real-time debugging tools (Reference 3) go a long way toward finding logical errors in multiprocessing software.

What a uniprocessor environment never reveals is time-related interactions between code sections. Even under a multitasking OS, a single processor can execute only one section of code at a time. Problems related to simultaneous or out-of-sequence code execution manifest only in the multiprocessor environment.

A new class of debugging tools has arisen that now operates in multiprocessor configurations. Table 1 gives a representative list of such tools; more are under development. One significant consideration in using multiprocessor debugging tools is the way in which they handle breakpoints. Some tools stop only the processor that executes the breakpoint. Others stop all processors in the system.

Tools that stop all processors act like traditional debugging tools extended to multiple processors. Both types attempt to freeze the system at a given state and then allow the designer to examine that state. Unfortunately, the debugging tool usually cannot shut off all processors simultaneously. If the tool has a direct link to each processor, the shutdown can occur quickly. If the tool must work through the operating system or if it controls the processors with software commands issued over the interprocessor-communications links, the shutdown can take milliseconds.

Tools need time to halt system

Because each processor shuts down independently, the frozen state does not represent an instant in time but, rather, a smear. Designers must be careful in interpreting the data that the tool gathers, making sure to account for the disparity in event timing. Designers should also make sure that delay timers don't time out and generate false error messages as the system is slowly shutting down.

Tools that stop only the processor executing the breakpoint are useful in applications in which the bulk of the system must continue operating. Control systems, for example, may need to continue operating while the designer examines the code under test. Stopping only one processor may introduce errors in the rest of the system, however. A system that uses daisy-chained interprocessor communications, for example, may find its communications channel blocked by the halted processor.

After the multiprocessing code is up and running, designers may find that the system's performance does not show the gains expected from the additional processing power. Performance-analysis tools can help identify optimization steps. By making a baseline-performance measurement in a single-processor system and then remeasuring performance after moving a task to a second processor, designers can empirically determine which tasks to distribute among the processors and which to keep together. Profiling tools can also help optimize multiprocessing systems. Sections of code in which the processors spend an unusually long time may suffer from deadlock or from clogged communications channels.

The combination of extended OS features and specialized debugging tools now available is rapidly making multiprocessing software development easier. OSs alone, however, cannot turn code designed for a single processor into efficient multiprocessing code. The OSs may automate some of the parallelization and distribution of code, but designers still need to direct those efforts. In addition, designers need to examine the implications of task distribution and execution sequence. Multiprocessing software development is becoming easier, but it's still not simple.

You can reach Technical Editor Richard A Quinnell (719) 530-0560, fax (719) 530-0560**, email ednquinnell@mcimail.com

References

1. Quinnell, Richard A, "Microkernel and modular OSs," EDN, April 13, 1995, pg 42
2. Quinnell, Richard A, "Distributed operating systems combine multiple processors into a single machine," EDN, Sept 28, 1995, pg 38.
3. Quinnell, Richard A, "Debugging real-time systems," EDN, Nov 23, 1994, pg 48.