If a person walks fast on a road covering fifty miles in a day, this does not mean he is capable of running unceasingly from... more

If a person walks fast on a road covering fifty miles in a day, this does not mean he is capable of running unceasingly from morning till night. Even an unskilled runner may run all day, but without going very far.

—Miyamoto Musahi, The Book of Five Rings

The most recent advances in microprocessor design for desktop computers involve putting multiple processors on a single computer chip. These multicore designs are completely replacing the traditional single core designs that have been the foundation of desktop computers. IBM, Sun, Intel, and AMD have all changed their chip pipelines from single core processor production to multicore processor production. This has prompted computer vendors such as Dell, HP, and Apple to change their focus to selling desktop computers with multicores. The race to control market share in this new area has each computer chip manufacturer pushing the envelope on the number of cores that can be economically placed on a single chip. All of this competition places more computing power in the hands of the consumer than ever before. The primary problem is that regular desktop software has not been designed to take advantage of the new multicore architectures. In fact, to see any real speedup from the new multicore architectures, desktop software will have to be redesigned.

The approaches to designing and implementing application software that will take advantage of the multicore processors are radically different from techniques used in single core development. The focus of software design and development will have to change from sequential programming techniques to parallel and multithreaded programming techniques.

The standard developer's workstation and the entry-level server are now multiprocessors capable of hardware-level multithreading, multiprocessing, and parallel processing. Although sequential programming and single core application development have a place and will remain with us, the ideas of multicore application design and development are now in the mainstream.

This chapter begins your look at multicore programming. We will cover:

• What is a multicore?

• What multicore architectures are there and how do they differ from each other?

• What do you as a designer and developer of software need to know about moving from sequential programming and single core application development to multicore programming?

... less

Please. As I was saying, she stumbled upon a solution whereby nearly ninety-nine percent of all test subjects accepted the... more

Please. As I was saying, she stumbled upon a solution whereby nearly ninety-nine percent of all test subjects accepted the program as long as they were given a choice, even if they were only aware of the choice at a near unconscious level.

—The Architect, The Matrix Reloaded

In this chapter we take a closer look at four multicore designs from some of the computer industry's leading chip manufacturers:

• The AMD Multicore Opteron

• The Sun UltraSparc T1

• The IBM Cell Broadband Engine (CBE)

• The Intel Core 2 Duo

Each of these vendors approaches the Chip Multiprocessor (CMP) differently. Their approaches to multicore design are implemented effectively with each design having its advantages, strengths, and weaknesses in comparison to the other designs. We will use these designs for all of the examples in this book. The program examples in this book have been compiled and executed on one or more of these multicore processor designs. In this chapter, we introduce you to the basics of each design, and throughout the book we fill in the necessary detail as it pertains to multicore application development and design.

In many mass market software applications, the differences between hardware implementations are abstracted away because often one of the primary design goals is to make the software compatible with as many different hardware platforms as possible. So there is a conscious effort to avoid platform-specific features. In these scenarios, the software designer and developer appropriately rely on the operating system to hide any platform differences that the applications might encounter. The developers move happily and blissfully through the development process without the burden of having to worry about hardware-specific issues. This is a good thing! One of the primary jobs of the operating system is to hide and manage hardware details. And this approach works for an entire class of mass market or wide vertical market applications.

However, not every kind of software developer is so lucky. For example, those developing high-transaction database servers, web servers, application servers, hardware-intensive game engines, compilers, operating system kernels, device drivers, and high-performance scientific modeling and visualization software are practically forced to look for and exploit platform features that will make their applications acceptable to the end user. For this class of developer, familiarity with a specific processor or family of processors is a prerequisite for effective software development.

... less

Assume we're facing multiple enemies and disperse the sets . . . Split up into four groups and activate the threshold triggers... more

Assume we're facing multiple enemies and disperse the sets . . . Split up into four groups and activate the threshold triggers!

—Shirow Masamune, Ghost in the Shell

Until recently, the most accessible tools and techniques used for software development were centered on notions from the sequential model of computer program execution. The basic (and often unstated) assumption in Information Technology (IT) and Computer Science programs at universities, colleges, and technical schools was that the software developer would be working in the context of single processor computers. This is evidenced by the fact that until recently educational institutions placed very little emphasis on the ideas of parallel programming. Two of the primary reasons for the lack of focus on parallel programming were cost and tradition.

• Cost: First, single processor computers were considerably cheaper and enjoyed a much wider availability than multiple-processor computers. Cost and availability made single processor computers the configuration of choice for most businesses, academic institutions, and government agencies.

• Tradition: Second, the fundamental ideas behind software development and computer programming were worked out decades ago within the constraints of single processor environments. Basic algorithms for searching, sorting, counting, parsing, and retrieving were developed, refined, and perfected under a sequential programming model. These same basic algorithms, data structures, programming models, and software engineering methodologies form the basis of most software development approaches in use today.

Sequential programming techniques are important and will always have their place. However, multiprocessor computer configurations are now widely available. This opens up a host of very different approaches to program decomposition and software organization. Software architectures that include a mix of sequential programming, multiprocessing, and multithreading will become common place. For the majority of developers these hybrid software architectures will be uncharted waters. The trend is that multiprocessor computers will in most cases replace single processor configurations in business, academia, and government. To take advantage of the multiprocessor environments, you as a software developer must add a new set of tools and techniques to your repertoire. Software projects that require multicore or parallel programming present unique challenges to software developers who are only accustomed to the sequential programming model, and this chapter addresses the challenges that developers face as they move into projects requiring multicore or parallel programming. We discuss the Software Development Life Cycle (SDLC) and methodologies as they apply to the concurrency model. Also, we discuss decomposing a problem as well as a solution, and procedural and declarative models.

... less

Functional Simplicity, Structural Complexity; The Best Life for All. That’s the maxim . . .

—Shirow Masamune,... more

Functional Simplicity, Structural Complexity; The Best Life for All. That’s the maxim . . .

—Shirow Masamune, Appleseed: The Promethean Challenge

So far we've described some of the primary challenges of multicore programming. We've briefly covered some of the notions of multithreading, multiprocessing, and multiprogramming. In Chapter 2, we introduced the Multicore Opteron, Cell, Duo Core 2, and UltraSparc T1. These chips represent four effective but very different approaches to multicore architectures. We explained how hardware-specific compiler switches are sometimes necessary to get to certain specific features of a Chip Multiprocessor (CMP). But we've said very little about the operating system's role in the design, development, and execution of multicore programs and applications. This chapter now turns to that topic. In this chapter we:

• Provide an overview of the operating system

• Discuss the developer's interface to the multiprocessor

• Explore how threads, processes, and processors are connected through the operating system

• Examine how the operating system Application Program Interfaces (APIs) and system calls are used in conjunction with C++ for multicore programming and application development

• Explain how the operating system functions as the gatekeeper of the multiprocessor

• Discuss how to use the Portable Operating System Interface (POSIX) standard to design and implement multicore applications that work on all major hardware and operating system platforms

... less

As long as I held the Divine Spear, I had to accept debugging as my primary duty.

—Tatsuya Hamazaki, .hack//AI Buster 2... more

As long as I held the Divine Spear, I had to accept debugging as my primary duty.

—Tatsuya Hamazaki, .hack//AI Buster 2

In Chapter 4, we looked at the operating system's role as a development tool for applications that required parallel programming. We provided a brief overview of the part that the operating system plays in process management and thread management. We introduced the reader to the notion of operating system Application Program Interfaces (APIs) and System Program Interfaces (SPIs), and in particular we introduced the POSIX API. In this chapter we are going to take a closer look at:

• Where the process fits in with C++ programming and multicore computers

• The POSIX API for process management

• Process scheduling and priorities

• Building C++ interface components that can be used to simplify part of the POSIX API for process management

Basically, a program can be divided into processes and/or threads in order to achieve concurrency and take advantage of multicore processors. In this chapter, we cover how the operating system identifies processes and how an application can utilize multiple processes.

... less

They come from a much older version of the matrix, but like so many back then, they caused more problems than they solved... more

They come from a much older version of the matrix, but like so many back then, they caused more problems than they solved.

—Persephone, Matrix Reloaded

In Chapter 5, we examined how concurrency in a C++ program can be accomplished by decomposing your program into either multiple processes or multiple threads. We discussed a process, which is a unit of work created by the operating system. We explained the POSIX API for process management and the several system calls that can be used to create processes: fork(), fork-exec(), system(), and posix_spawn(). We showed you how to build C++ interface components, interface classes, and declarative interfaces that can be used to simplify part of the POSIX API for process management. In the chapter we cover:

• What is a thread?

• The pthread API for thread management

• Thread scheduling and priorities

• Thread contention scope

• Extending the thread_object to encapsulate thread attribute functionality

... less

There is only one constant, one universal. It is the only real truth; causality. Action, reaction. Cause and effect.... more

There is only one constant, one universal. It is the only real truth; causality. Action, reaction. Cause and effect.

—Merovingian, Matrix Reloaded

In Chapter 6, we discussed the similarities and differences between processes and threads. The most significant difference between threads and processes is that each process has its own address space and threads are contained in the address space of their process. We discussed how threads and processes have an id, a set of registers, a state, and a priority, and adhere to a scheduling policy. We explained how threads are created and managed. We also created a thread class.

In this chapter, we take the next step and discuss communication and cooperation between threads and processes. We cover among other topics:

• Communication and cooperation dependencies.

• Interprocess and Interthread Communication

• The PRAM model and concurrency models

• Order of execution models

• Object-oriented message queues and mutexes

• A simple agent model for a pipeline

... less

Even if parallel processing is done on a project, there really isn't much change in actual processing efficiency—there's... more

Even if parallel processing is done on a project, there really isn't much change in actual processing efficiency—there's just a diversity of output.

—Shirow Masamune, Ghost in the Shell: Man-Machine Interface

Chapter 4 illustrated the role the operating system plays for applications that have a requirement for parallelism or multicore support. In it, we explained how the processes and kernel threads are the only execution units that the operating system schedules for processor execution. In Chapters 5 and 6, we explained how processes and threads are created and are used to gain access to Chip Multiprocessors (CMPs), but processes and threads are relatively low-level constructs. The question remains, “How do you approach application design when there is a concurrency requirement or when the design model has components that can operate in parallel?” In Chapter 7, we explored mechanisms that support Interprocess Communication (IPC): mutexes, semaphores, and synchronization. These are also low-level constructs that require intimate knowledge of operating-system-level Application Program Interfaces (APIs) and System Program Interfaces (SPIs) in order to program correctly.

So far we have discussed only scenarios that involved dual or quad core processors. But the trend in CMP production will soon replace dual and quad core processors. The UltraSparc T1, which we introduced in Chapter 2, has eight cores on a single chip with four hardware threads for each core. This makes it possible to have 32 processes or threads executing concurrently. Currently dual and quad core CMPs are the most commonly found configurations. However, dual and quad core configurations will soon be replaced by octa-core CMPs like the UltraSparc T1. So, how do you think about application design when 32 hardware threads are available? What if there are 64, 128, or 256 processors on a single CMP? How do you think about software decomposition as the numbers of available hardware threads approach the hundreds? This chapter turns to those questions by discussing:

• A design approach for applications to run on multiple processor cores

• The PADL and PBS approach to application design

• Task-oriented software decompositions and declarative and predicate-oriented decompositions

• Knowledge sources and multiagent architectures

• Intel Thread Building Blocks (TBB) and the new C++ standard that supports concurrency

... less

The topology of perceived interconnected cyberspaces need not have any direct connection to that of the array of support... more

The topology of perceived interconnected cyberspaces need not have any direct connection to that of the array of support computers, since the cyberspaces are perceived, not actual spaces.

—Marcus Novak, Liquid Architectures in Cyberspaces

A model of a system is the body of information gathered for the purpose of studying the system so that it can be better understood by the developers and maintainers of the system. When a system is modeled, the boundaries and identification of the entities, attributes, and activities performed by the system can be determined. Modeling is an important tool in the design process of any system. It is essential that developers fully understand the system they are developing. Modeling can reveal the hidden concurrency and opportunities where parallelism can be exploited.

In this chapter, we show you how to visualize and model your concurrent system using the UML. We will discuss diagraming techniques used to visualize and model concurrent systems from three perspectives:

• The structural perspective

• The behavioral perspective

• The architectural perspective

type="note"

The classes, objects, processes, threads, and systems used as examples in this chapter are used for exposition purposes and may or may not necessarily reflect actual classes, objects, or structures used in an actual system. This chapter should not be considered a primer for UML but rather an introduction to the diagrams used in this book focused on the UML notation used to design and document systems that utilize concurrency.

... less

Those are places that can't be accessed from a Chaos Gate. If you try to enter, you show up, see a warning indicator, and... more

Those are places that can't be accessed from a Chaos Gate. If you try to enter, you show up, see a warning indicator, and then you're warped back to town.

—Miu Kawasaki, .hack// Another Birth

In Chapter 8, we introduced the Predicate Breakdown Structure (PBS) of an application and the Parallel Application Design Layers (PADL) analysis model. These are top-down approaches to producing declarative architectures for applications that have a concurrency or parallel programming requirements. One of the ultimate goals of PBS and PADL is to establish a chain of possession or audit trail for the application concurrency requirements that lead from the solution model to threads or processes at the operating system level. In this chapter, we connect the PBS and PADL analysis to application software testing and exception handling. The PBS and PADL tell you what you should be testing for and what constitutes an error or an exception. You can use exception handling to provide a kind of logical fault-tolerance for declarative architectures. That is, if your application for unknown and uncontrollable reasons violates statements, assertions, rules, predicates, or constraints from the PBS, you want to throw an exception and gracefully exit because once the predicates have been violated, then the correctness, reliability, and meaning of the application has been compromised.

In this chapter, we also introduce the various types of testing that should be part of any Software Development Life Cycle (SDLC), especially ones where parallel programming will be deployed. We explain exception handling, the differences between error handling and exception handling, some of the issues for multithreading and parallel programming. We also briefly introduce the notion of model checking, the relevance of possible-world semantics to the declarative interpretation of parallel programming, and how they are used for testing and exception handling.

Specifically, in this chapter we will cover the following:

• Connecting the PBS and PADL analysis to application software testing and exception handling

• Explaining the various types of testing that should be part of any SDLC

• Defining exception handling and what the differences are between error handling and exception handling

• Introducing to the notion of model checking and the relevance of possible-world semantics to the declarative interpretation of parallel programming

... less

This appendix provides a quick reference to the UML diagrams used throughout this book. The Unified Modeling Language... more

This appendix provides a quick reference to the UML diagrams used throughout this book. The Unified Modeling Language (UML) is a graphical notation used to design, visualize, model, and document the artifacts of a software system. It is the de facto standard for communicating and modeling object-oriented systems. The modeling language uses symbols and notations to represent the artifacts of a software system from different views and with different focuses. Although there are other graphical notations and artifacts used in this book, this appendix provides a quick way the reader can become familiar with the basic UML notations and symbols they may require in documenting their software systems.

... less

This appendix provides a quick reference to the concurrency models used in this book. Concurrency models determine how concurrent... more

This appendix provides a quick reference to the concurrency models used in this book. Concurrency models determine how concurrent tasks delegate work to the tasks and how communication is performed. The models can also supply a structure and approach that will assist you in determining the access policies. Here, we compiled the concurrency models with a short definition and diagram for each model.

... less

This appendix contains sections from the POSIX Standard for Thread Management. Portable Operating System Interface... more

This appendix contains sections from the POSIX Standard for Thread Management. Portable Operating System Interface (POSIX) is the open operating system interface standard accepted worldwide. It is produced by IEEE and recognized by ISO and ANSI. Support of POSIX standards ensures code portability between systems and is increasingly mandated for commercial applications and government contracts. The POSIX Standard in the most widely available method for cross-platform multicore development. It is compatible with high-level thread libraries such as Solaris Threads, Intel Thread Building Block, and the new Standard C++0x. The POSIX Standard is voluminous, containing thousands of pages. Here, for your convenience, are sections from the standard on thread management. The API functions contained in these sections are either covered in this book or are of concern when developing multicore applications.

The following excerpts are reprinted with permission from IEEE Std. 1003.1-2001, IEEE Standard for Information Technology - Portable Operating System Interface (POSIX), Copyright 2001, by IEEE. The IEEE disclaims any responsibility or liability resulting from the placement and use in the described manner.

... less

This appendix contains sections from the POSIX Standard for Process Management. Portable Operating System Interface... more

This appendix contains sections from the POSIX Standard for Process Management. Portable Operating System Interface (POSIX) is the open operating system interface standard accepted worldwide. It is produced by IEEE and recognized by ISO and ANSI. Support of POSIX standards ensures code portability between systems and is increasingly mandated for commercial applications and government contracts. The POSIX Standard is the most widely available method for cross-platform multicore development. It is compatible with high-level libraries such as the Standard Template Adaptive Parallel Library (STAPL) and new Standard C++0x. The POSIX Standard is voluminous, containing thousands of pages. Here for your convenience are selected sections from the standard on process management. The API functions contained in these selected sections were either covered in this book or are of concern when developing multicore applications.

The following excerpts are reprinted with permission from IEEE Std. 1003.1-2001, IEEE Standard for Information Technology - Portable Operating System Interface (POSIX), Copyright 2001, by IEEE. The IEEE disclaims any responsibility or liability resulting from the placement and use in the described manner.

... less