Design Feature: July 18, 1996

Today, multiprocessor-system design falls within the scope of even small design teams with modest budgets. From a hardware perspective, a custom multiprocessor design for a specific application can prove technologically and economically feasible. In particular, the new µP architectures greatly simplify tightly coupled, two- and four-processor designs. In addition, the IEEE scalable-coherent-interface (SCI) standard promises to simplify integrating greater numbers of processors.

Multiprocessing designs range from loosely coupled architectures, in which each processing node has a dedicated copy of the operating system (OS) and application programs to tightly coupled architectures in which a single copy of the OS and application programs are executed across several processors (Figure 1). It's the tightly coupled end of the spectrum in which processor vendors and the SCI standard have made inroads into simplifying hardware design. In the general-purpose computing market, most designers choose a tightly coupled architecture, because writing code for such a system is simpler. (For developments in loosely coupled architectures see box, "Fast links loosely couple nodes.")

Despite the promised simplicity, there are at least three major aspects to designing a multiprocessor system. First, you must develop the architecture and logic to allow a tightly coupled system to share a single main-memory subsystem across multiple processors. Just a year or two ago, this phase was, by far, the most difficult aspect of multiprocessor-system design. Today, however, µP, ASIC, and board vendors offer products that greatly simplify this task.

Despite the help in the architecture-design phase, if you work from the chip level, you still face the challenge of high-speed circuit-board design and layout. The processor and bus clocks in multiprocessor designs start at 40 MHz and increase to hundreds of megahertz, so designing an optimal system requires substantial expertise. One option is to use board-level products and partially or fully relegate the high-speed board-design task to the vendor.

Software issues comprise the third major task in multiprocessor-system development. Tightly coupled systems most often depend on symmetric-multiprocessing (SMP) OSs as a software base. In a multitasking environment, such an OS can seamlessly dispatch application programs that need service to the next available processing element. Microsoft Windows NT, most flavors of Unix, and even some real-time OSs offer SMP capabilities.

In some cases, SMP OSs simplify the software portion of the multiprocessing design task. For example, consider a database server that uses multiple processors to extend the number of user tasks or queries that the system can concurrently execute. The application programs are identical whether on an SMP system or on a traditional single-processor system.

Many scientists and engineers, however, may want to use a multiprocessor design to accelerate a single computationally intensive application. To advantageously host a single application on an SMP system, you must rethink and rewrite that application. In the simplest case, you have to break the application into smaller ones that can concurrently run on different µPs, and you must handle data and synchronization dependencies among the smaller modules. (See"OSs and development tools lighten the load," by Richard A Quinnell, which discusses programming tools and techniques.)

Getting back to hardware architectures, let's consider the requirements of a tightly coupled system and how you can design one. A tightly coupled design uses a number of processors and only one main-memory array. In the simplest case, you can connect the buses of a number of µPs to a single memory controller and memory array. Even single-processor, multitasking systems rely on one task to lock a memory segment during runtime to prevent another task from reading potentially stale data. The memory-management unit (MMU), found on most µPs, implements this standard feature that solves memory-contention problems in a multitasking, single-processor or multiprocessor system.

You can couple two Pentium processors to main memory in this manner. Unfortunately, the proposed design offers poor performance for several reasons. One reason is that most DRAM used as main memory is too slow to support processors operating at full speed. You could solve this problem with more expensive SRAM as main memory, but you would run into a second problem: bus contention. With a shared bus, one processor must wait to access memory when the other is reading or writing memory.

You can solve the first problem by using cache. The Pentium, in fact, includes a 16-kbyte on-chip cache; however, even single-processor systems require level-2 (L2) cache for maximum performance. Moreover, because of bus contention, misses to the on-chip cache in a multiprocessor system can exaggerate latencies. For processors to effectively share a bus, your design must minimize the number of accesses to that bus, so that one processor doesn't regularly wait for a second processor to clear the bus.

Theoretically, as you add processors, a multiprocessor design should scale almost linearly in performance. The proposed simplistic example certainly does not double in performance with two processors. In fact, the system offers little performance gain over a single-processor design.

An effective cache dedicated to each processor can solve the bus-contention problem by keeping most memory accesses off the shared bus. Moreover, a well-de-signed cache is the key to feeding a fast processor with little or no latency. The mod-el of L2 cache dedicated to each processor with a shared main memory has proven to be the most effective tightly coupled architecture.

Unfortunately, caches introduce an obstacle because multiple caches can simultaneously hold copies of the same data. If a task on one processor modifies a cached-memory location, other caches holding the data must be kept coherent, or the entries in the other caches would be invalid. In fact, the two Pentium µPs mentioned would be subject to this problem because of the on-chip caches. The Pentium, however, includes the capability of cache coherency in a dual-processor configuration, and you must address the issue of cache coherency in any multiprocessor design.

Your design must adapt or add to three aspects of traditional cache design for multiprocessor systems. Cache tags are the first aspect. In a single-processor design, cache tags simply use two states, valid or invalid, to indicate whether a task can read valid data from an individual cache line. Multiprocessor systems require more tag states.

The second feature is the main-memory-and-remote-cache-update strategy. Single-processor systems use either a write-through or -back strategy. Write-through caches update main memory any time a write occurs in the cache. Write-back schemes wait until the cache line is flushed before updating main memory. Write-through is simpler to implement but results in the latency of a write to main memory each time data is written to the cache. Most designs use a write-back strategy, although several variations of the write-back exist in multiprocessor systems because of the presence of other caches that could store copies of the same memory locations. For example, when writing to a cache line, some designs automatically invalidate main memory and any other instances of the memory location in other caches.

The third aspect of multiprocessor-cache design is the snooping mechanism, which each processing node uses to monitor operations in other nodes. Single-processor systems require no bus snooping. To maintain cache coher-ency, a multiprocessor design requires some form of snooping or a central directory of cached information.

Most multiprocessor-enabled µPs, multiproccesor ASICs, boards, and systems use a multistate cache-tag architecture to help maintain coherency. The most common cache-tag scheme is the modified-exclusive-shared-invalid (MESI), and Table 1 depicts the Intel Pentium and Pentium Pro implementation. The table assumes a write-back cache algorithm in which a modified cache line isn't generally written through to main memory until the line is flushed from cache or until another processor requests that memory location.

The MESI scheme relies on a four-state cache tag. The modified state indicates that the data line is available only in the local cache. The local cache controller is responsible for either writing the modified data to main memory or snooping read operations to main memory to detect any instance of another processor's requesting the data. The exclusive state indicates that the line is available only in the local cache and the local processor has not modified the line. The shared state indicates that the cache line may exist in the cache of other processors. A write to a shared line typically is written through to main memory, and any instances of the line in other caches are invalidated.

The invalid state indicates the absence of the data requested (a cache miss) and generates a line fill from main memory. In a write-back implementation, the line fill could be delayed if the data requested is present in one of the other caches. The controller for the cache holding the data typically snoops the read, signals the requesting processor to delay, and writes the requested data to main memory.

Coherent and error-free bus

Cache-architecture and -controller design is the most important element in a multiprocessing architecture. Fortunately, in many cases, you don't have to develop such an architecture from the ground up to design a multiprocessor system.

For example, the Pentium guarantees coherency only in a two-processor design with no L2 cache. Third-party-vendor Corollary, however, offers a Pentium-specific multiprocessor de-sign to OEMs. Corollary's implementation supports as many as eight processors and is based on the company's C-bus II multiprocessor architecture and Simpl chip set. The multiplexed, 64-bit, 50-MHz C-bus II transfers data as fast as 400 Mbytes/sec and includes provisions for MESI-based cache coherency, error checking and correction (ECC) on all address and data cycles, and support for standard I/O through the PCI bus.

The Simpl chip set in-cludes the $180 (1000) Cache Bus Controller (CBC), the $80 (1000) Data Path Exchange (DPX), the $240 (1000) PCI Bridge (PCIB), and the $75 (1000) Cache Bus Memory Controller (CMC) ICs. In addition to a Pentium µP, a typical processing node includes a CBC IC, two DPX ICs, four burst-cache RAMs, and two RAM ICs for cache tags. The DPX ICs buffer data among the C-bus II, the processor, and the cache, and the CBC interfaces with the cache and tag RAM. The CMC is used on DRAM-based main- memory boards to interface with the C-bus II, and the PCIB is used on I/O cards.

Corollary goes beyond a minimal multiprocessor implementation. The ECC capability enhances reliability, the design incorporates both L2 and level-3 (L3) caches, and the bus interfaces include buffers that decouple the processor data buses from the C-bus II. The direct-mapped L2 cache can range from 256 kbytes to 2 Mbytes per processor. Actually a peer to the L2 cache, the L3 cache stores only six cache lines. The L3 cache is fully associative, however, so each entry can cache any line in main memory. Corollary calls the L3 cache a "victim cache," because it solves pathological cases in which the ill-conceived software would constantly thrash the L2 cache. The Pentium's on-chip cache can directly read data through the CBC from either the L2 or L3 cache.

Corollary's advantage is its fully integrated and tested system. In fact, you can buy systems or boards rather than ICs. Moreover, the Pentium is perhaps the most attractive processor from a price perspective, because even at low volume, 166-MHz parts cost well under $500.

From an architectural perspective, the most important aspect of Corollary's design is the formalization of a secondary systemlike bus, which is independent of the local processor bus. Silicon vendors have also adopted this strategy.

The SPARC community, including Sun, was among the first in the industry to realize the advantages of a formalized secondary bus. The community's MBus architecture is more than five years old. Early on, MBus was primarily important, because it allowed vendors of SPARC-compatible microprocessors to adopt significantly different design philosophies. For example, some implementations used virtually addressed caches—cache addressed before MMU virtual-to-physical address translation. Other versions used physically addressed caches. At the module level, however, you could plug either version into an MBus-compliant motherboard, because the caches were on the module.

MBus was a boon to multiprocessing design, because the modules could host multiple µPs, and vendors could design systems to host more than one module. Today, Ross Technology is the most aggressive marketer of MBus technology. The company offers one- and two-processor HyperSPARC modules, which can also include from 256 kbytes to 1 Mbyte of L2 cache. Depending on the number and speed of processors, the amount of cache, and OEM volumes, the modules cost $900 to $7000.

Ross' HyperSPARC modules host one or more RT620 µPs, one or more RT625/626 cache controllers, and a number of cache RAMs. The modules implement a MESI-type cache-controller scheme and demonstrate a way in which some vendors add value in the area of cache design. Ross' modules eliminate some of the latency that a processor incurs when trying to access a memory line that's stored in another cache (Figure 2). The Direct Data Intervention with Memory Reflection scheme lets the snooping controller directly transfer the needed data line to the requesting cache and automatically update main memory.

Like those who jump on the bandwagon after the football team has won, most other major processor vendors have endorsed the secondary- or multiprocessor-bus concept. They've also adopted the term "glueless multiprocessing," although the implementations require some level of cache or memory controllers.

The Motorola/IBM PowerPC 604, for example, offers designers the ability to connect as many as four µPs with minimal trouble. As is the case with most processors, four isn't a hard limit but, rather, the limit for loads that can be connected to a single CMOS bus. The PowerPC design syndicate has closely specified the multiprocessing bus timing but has not specified a modular interface or connector for MBus-like modules.

Without using glue logic, you can directly connect the processors, but you limit your design to the 32-kbyte on-chip caches. The companies claim that you can implement an L2-cache controller with a simple pass-through buffer that extends the processor bus. Motorola has developed a combination PCI-bridge, L2-cache-controller, and main-memory-controller IC, the MPC105, for single-processor systems. The single-processor-system-controller chip costs about $30 (1000), and the company is working on a multiprocessor version of the chip, the MPC106, with price and availability to be determined. A 100-MHz 604 costs $302 (1000).

In multiprocessor design, Mips has supported some level of multiprocessing in the instruction set since the advent of the R4000 family, about three years ago. The new R10000 comes with separate L2-cache and system interfaces. Mips calls the system interface the "Cluster Bus," and on-chip cache controllers provide a relatively glueless four-processor design.

The R10000 offers the advantage of three cache-coherency schemes, but neither Mips nor its semiconductor partners, NEC and Toshiba, offer the required Cluster Controller IC. You can design a relatively simple memory controller to support standard snooping-based systems. More complex schemes include a snoop-based scheme with secondary copies of the cache tags stored in the Cluster Controller. A second copy of the tags eliminates the need for the L2-cache controllers to snoop external operations, thereby eliminating snooping latencies. The third scheme, a centralized, directory-based implementation, primarily targets designs with more than four µPs. NEC and Toshiba have not announced whether they will offer an off-the-shelf Cluster Controller. The other drawbacks of the processor are the price, which is still around $3000, and the processor's limited availability.

Intel offers perhaps the most glueless four-processor scheme via the Pentium Pro family. Intel not only defines separate cache and system interfaces, but also sells the Pentium Pro only prepackaged with cache. You can connect four Pentium Pro µPs with no glue logic other than a main-memory controller. For the Pentium Pro, Intel has announced the 82450 core-logic chip sets, which include a main-memory controller and assorted other functions. Using the chip set, you can connect a quad cluster of Pentium Pro µPs to resources such as main memory and the PCI bus. The chip sets range in price from $209 (1000) to $291 (1000), depending on features and low-volume street prices of Pentium Pro ICs range from $500 to $700 for speeds from 150 to 200 MHz.

You may be able to directly buy four-processor boards from Intel on an OEM basis, depending on volume. Several third parties and system OEMs have made reference to the Standard High Volume Server (SHVS) platform, which Intel will purportedly sell on an OEM basis, as it does PC motherboards. For now, Intel hasn't announced the SHVS, and it may never publicly announce such a product, because the sales channel is strictly large-volume OEM customers. Despite the cloak of secrecy, the SHVS board includes sites for two processor modules—each of which can host two Pentium Pro µPs. The design also supports PCI and other types of I/O.

UPA: an architectural concept

At this point, you may be convinced that a standardized multiprocessor bus is central to your design. Sun, which was key in starting the trend with MBus, however, has taken a decidedly different direction. The company's new UltraSPARC-based designs use the UltraSPARC Port Architecture (UPA).

For now, UPA, as it relates to multiprocessor-system design, is a proprietary technology. Sun sells UltraSPARC µPs and core-logic chip sets for single-processor implementations. Whether the company will also sell the multiprocessor implementations that it is currently shipping in workstation and server products is unclear.

UPA isn't a bus; rather, it is a more system-level architectural concept for maximizing the concurrent use of multiple datapaths in a system. Sun has defined bus timing that's consistent for all datapaths in a UPA-based system. All datapaths operate at 83 MHz and can vary in width from 32 to 128 bits with 1 additional bit/byte dedicated to ECC.

UPA maintains the concept of separate connections for L2 cache and the main processor interface. The system interface, however, connects to a buffered crossbar switch. Other switch ports might connect to the graphics or I/O subsystem, the main memory, or the system controller. In Sun's current two-processor workstation implementation, a 144-bit (128 data bits plus a 16-bit ECC) shared path connects the processors to the crossbar. Dual data- paths provide a 288-bit connection to DRAM, and the graphics and I/O subsystems share a 72-bit path.

One UPA port in the processing node must act as master, and the others must act as slaves. The system controller is responsible for cache coherency throughout the system and maintains coherency by snooping transactions that go through the crossbar. The controller maintains a secondary copy of the L2 cache tags from each processor. This action eliminates constant access of the L2-cache tags in the processor-based cache controller and frees the cache controller to supply data to the processor with minimal latency.

The most unique aspect of UPA is that no specification determines the exact design. For example, a four-processor design could connect the µPs on one shared datapath or could dedicate a separate datapath to each µP. The system designer makes the decision based on cost/performance trade-offs, but the UPA architecture and cache- coherency protocols allow for either option.

In a sense, Sun has just moved the user-visible interfaces one or more steps farther away from the microprocessor than Mbus, for example. Besides memory sockets, the user or system integrator may not have access to any interface other than the PCI I/O interface. Sun's philosophy is if this approach can offer compelling performance, the customer doesn't care which interfaces are in the box. On the other hand, UPA leaves you with a sense of dŽjˆ vu, because you know you've seen closed systems before.

Sun has also used UPA in server systems with as many as 30 processors. The servers actually use dual-processor elements similar to those in the workstation implementation. The servers connect the elements with a proprietary scheme called "gigaplane."

Time will determine whether UPA becomes a market winner. Regardless of your opinion of UPA, you must use the best tools that you can buy today in your design. Even if your application requires more than four processors, you have many choices.

The most exciting development in connecting more than four processors comes via products designed to the IEEE 1596 SCI standard. SCI defines both a physical-layer interface and higher layer protocols for maintaining cache coherence at each node. The physical interface can use fiber, coaxial-serial cables, or parallel cables. You can connect the interface in a ring topology or via a crossbar switch. Maximum point-to-point bandwidth is 1 Gbyte/sec, and the standard also allows for lower speed modes. The industry developed SCI with the knowledge that it couldn't offer the low latency of a multiprocessor bus but with the understanding that even the most robust bus designs can't support more than 32 processors and that four is a limit for most.

SCI uses a distributed directory-based scheme to maintain cache coherency among all nodes. For each shared-memory line in the multiprocessor system, a list identifies each node with a cached copy of the line. An SCI controller can view the local copy of the directory and make requests across the SCI interface when desired data resides in another node.

Dolphin Interconnect Solutions has established a leadership position in the SCI arena. The company has developed SCI ICs, boards, and a crossbar switch. Perhaps the easiest way to understand SCI is through an examination of Dolphin's Pro-SCI card for Pentium-Pro-based designs.

Dolphin designed the Pro-SCI for the four-processor Intel SHVS model. SCI lets you connect any number of quad modules (theoretically, up to the SCI limit of 65,520) via cables and still maintain coherency throughout the system. At least one version of the SHVS that's being developed in partnership by Data General and Dolphin includes a connector for the Pro-SCI board (Figure 3).

Think of the main memory on any four-processor node as an L3 cache to the memory that exists throughout the rest of the system. A local-memory access that misses in the L2 caches is typically handled by Intel's memory controller in the 82450 chip set. Intel designed the memory controller, however, to accommodate both the local DRAM array and far memory located at other nodes. If the read also misses in the local DRAM, the memory controller passes the request along to the CDC IC on Dolphin's board. The CDC connects to local memory that stores the SCI directory and to one or more LinkController ICs that implement the packet-based communications with other nodes.

The only kinks in the SCI-based system are the differences in latency between reads to local and far memory, via the Dolphin board. Intel accommodates these differences via a defer cycle in the Pentium Pro architecture. On a read to far memory, the Pentium Pro doesn't wait for the data but, rather, continues operation either through out-of-order instruction execution or via a context switch to another application. When the Intel memory controller receives data from the far memory, the controller can flag the data with an ID unique to the original request and write the data onto the shared processor bus.

Dolphin and Data General will both sell the Pro-SCI board. Dolphin has prototypes now and expects OEM prices of approximately $2500, based on volume and onboard memory. Data General plans to use the board in its own systems and to sell multiprocessing building blocks to OEMs. Data General, in fact, is rumored to be working with the Santa Cruz Operation (Santa Cruz, CA) to add support for SCI and the Pro-SCI board to the UnixWare OS.

And, as if we don't have enough acronyms, the SCI-based architecture is being called "nonuniform memory access" (NUMA), or "cache-coherent NUMA" (CC-NUMA). The acronyms simply refer to the fact that not all memory reads need to be resolved in local memory. It's important that you know the term "NUMA," because you will see it a lot over the next year. Unfortunately, different vendors have decidedly different plans for NUMA products—so be prepared to look under the hood and examine exactly what it means in each case. Sequent Computer Systems has several white papers on its Web site at http://www.sequent.com that address the terminology and architectural issues.

Sequent, in fact, plans to be a major player in SCI-based NUMA systems but has yet to announce SCI-based products. The company does plan to sell the technology down the road on an OEM basis in a similar manner to Data General and to offer the technology in system products.

Be on the lookout, meanwhile, for other SCI products. Vitesse Semiconductor (Camarillo, CA) is rumored to have an SCI data-pump IC in the wings. Dolphin has announced a PCI-bus-to-SCI bridge that sells for less than $1000 and plans an SBus-to-SCI bridge, which will cost less than $2000.

These bridge products suggest yet another aspect of SCI that could be important to your designs. You can use SCI as a message-passing interface as well as a cache-coherent bus. Dolphin expects that SCI bridge boards will offer an economical way to loosely couple servers, and Novell (South Provo, UT) will likely offer a clusterable version of NetWare next year. Dolphin, meanwhile, is working on a port of Windows NT to the PCI-to-SCI bridge.

Dolphin also is promoting a new architecture, called "snugly coupled," in which a single application program can operate across multiple processing nodes, each of which has its own copy of the OS. Snugly coupled designs promise to make programming just as simple as in tightly coupled systems and to allow the overall system to continue to run even if one node fails. This year, Dolphin plans to announce what it calls "middleware," which will enable standard applications to run on a snugly coupled system.

Go to our special coverage on multiprocessing.

You can reach Technical Editor Maury Wright at (619) 748-6785; fax (619) 679-1861; email ednwright@mcimail.com