Professional Multicore Programming: Design and Implementation for C++ Developers

Published by

Wiley Publishing, Inc.

10475 Crosspoint Boulevard

Indianapolis, IN 46256

www.wiley.com

Copyright © 2008 by Wiley Publishing, Inc., Indianapolis, Indiana

Published simultaneously in Canada

ISBN: 978-0-470-28962-4

Library of Congress Cataloging-in-Publication Data

Hughes, Cameron, 1960-

Professional multicore programming : design and implementation for C++ developers/Cameron Hughes, Tracey Hughes.

p. cm.

Includes index.

ISBN 978-0-470-28962-4 (paper/website)

1. Parallel programming (Computer science) 2. Multiprocessors. 3. C++ (Computer program language) 4. System design. I. Hughes, Tracey. I. Title.

QA76.642.H837 2008

005.13'3—dc22

2008026307

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Legal Department, Wiley Publishing, Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, (317) 572-3447, fax (317) 572-4355, or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Web site may provide or recommendations it may make. Further, readers should be aware that Internet Web sites listed in this work may have changed or disappeared between when this work was written and when it is read.

For general information on our other products and services please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Wrox Programmer to Programmer, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book.

Excerpts from the POSIX Standard for Thread Management and the POSIX Standard for Process Management in Appendixes C and D 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.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

We would like to dedicate this book to Vera and Mary, our inspiration.

About the Authors

Cameron Hughes is a professional software developer. He is a software engineer at CTEST Laboratories and a staff programmer/analyst at Youngstown State University. With over 15 years as a software developer, Cameron Hughes has been involved in software development efforts of all sizes, from business and industrial applications to aerospace design and development projects. Cameron is the designer of the Cognopaedia and is currently project leader on the GRIOT project that runs on the Pantheon at CTEST Laboratories. The Pantheon is a 24 node multicore cluster that is used in the development of multithreaded search engine and text extraction programs.

Tracey Hughes is a senior graphics programmer at CTEST Laboratories, where she develops knowledge and information visualization software. Tracey Hughes is the lead designer for the M.I.N.D, C.R.A.I.G, and NOFAQS projects that utilize epistemic visualization at CTEST Laboratories. She regularly contributes to Linux development software efforts. She is also a team member on the GRIOT project.

Cameron and Tracey Hughes are also the authors of six books on software development, multithreaded, and parallel programming: Parallel and Distributed Programming Using C++ (Addison Wesley, 2003), Linux Rapid Application Development (Hungry Minds, 2000), Mastering the Standard C++ Classes (Wiley, 1999), Object-Oriented Multithreading Using C++ (Wiley, 1997), Collection and Container Classes in C++ (Wiley, 1996), and Object-Oriented I/O Using C++ Iostreams (Wiley, 1995).

Credits

Executive Editor

Carol Long

Senior Development Editor

Kevin Kent

Technical Editor

Andrew Moore

Production Editor

Christine O’Connor

Copy Editor

Foxxe Editorial Services

Editorial Manager

Mary Beth Wakefield

Production Manager

Tim Tate

Vice President and Executive Group Publisher

Richard Swadley

Vice President and Executive Publisher

Joseph B. Wikert

Project Coordinator, Cover

Lynsey Stanford

Proofreader

Christopher Jones

Indexer

Robert Swanson

Acknowledgments

As with all of the projects that we are fortunate to be involved with these days, we could not have made it to the finish line without the help, suggestions, constructive criticisms, and resources of our colleagues and friends. In particular, we would like to thank the YSU student chapter of the ACM for suffering through some of the early versions and rough drafts of the material presented in this book. They were single-handedly responsible for sending us back to the drawing board on more than one occasion. We are indebted to Shaun Canavan for providing us with release time for this project and for picking up the slack on several of the colloquiums and conferences where we had major responsibilities but not enough time to execute them. We would like to thank Dr. Alina Lazar for excusing us from many missed meetings and deadlines. A big thanks goes to Trevor Watkins from Z Group who gave us free and unrestricted access to Site B and for helping us with Linux and the Cell processors. We owe much gratitude to Brian Nelson from YSU who patiently answered many of our pesky questions about the UltraSparc T1 Sun-Fire-T200 and for also giving us enough disk quota and security clearance to get the job done! Thanks to Dr. Kriss Schueller for his inspiring presentation to our group on multicore computing and the UltraSparc T1 and also for agreeing to review some of the early versions of the hardware material that we present in the book. A special thanks goes to CTEST Labs who gave us full access to their Pantheon cluster, multicore Opterons, and multicore Macs. The CTEST Pantheon provided the primary testing resources for much of the material in this book. We would like to thank Jacqueline Hansson from IEEE for her help with the POSIX standards material. Thanks to Greg from Intel who helped us get off to a good start on the Intel Thread Building Blocks library. Thanks to Carole McClendon who saw value in this project from the very beginning and who encouraged us to see it through. A book of this nature is not possible without the input from technical editors, development editors, and reviewers. We have to extend much appreciation to Kevin Kent, our senior development editor, who helped sculpt the material and for providing us with very useful criticism and input throughout the project; to Carol Long, our executive acquisitions editor for her support as we tip-toed past our share of deadlines; to Andrew Moore, our technical editor; and to Christine O’Connor, our production editor.

Introduction

The multicore revolution is at hand. Parallel processing is no longer the exclusive domain of supercomputers or clusters. The entry-level server and even the basic developer workstation have the capacity for hardware- and software-level parallel processing. The question is what does this mean for the software developer and what impact will it have on the software development process? In the race for who has the fastest computer, it is now more attractive for chip manufacturers to place multiple processors on a single chip than it is to increase the speed of the processor. Until now the software developer could rely on the next new processor to speed up the software without having to make any actual improvements to the software. Those days are gone. To increase overall system performance, computer manufacturers have decided to add more processors rather than increase clock frequency. This means if the software developer wants the application to benefit from the next new processor, the application will have to be modified to exploit multiprocessor computers.

Although sequential programming and single core application development have a place and will remain with us, the landscape of software development now reflects a shift toward multithreading and multiprocessing. Parallel programming techniques that were once only the concern of theoretical computer scientists and university academics are in the process of being reworked for the masses. The ideas of multicore application design and development are now a concern for the mainstream.

Learn Multicore Programming

Our book Professional Multicore Programming: Design and Implementation for C++ Developers presents the ABCs of multicore programming in terms the average working software developer can understand. We introduce the reader to the everyday fundamentals of programming for multiprocessor and multithreaded architectures. We provide a practical yet gentle introduction to the notions of parallel processing and software concurrency. This book takes complicated, almost unapproachable, parallel programming techniques and presents them in a simple, understandable manner. We address the pitfalls and traps of concurrency programming and synchronization. We provide a no-nonsense discussion of multiprocessing and multithreading models. This book provides numerous programming examples that demonstrate how successful multicore programming is done. We also include methods and techniques for debugging and testing multicore programming. Finally, we demonstrate how to take advantage of processor specific features using cross-platform techniques.

Different Points of View

The material in this book is designed to serve a wide audience with different entry points into multicore programming and application development. The audience for this book includes but is not limited to:

Library and tool producers

Operating system programmers

Kernel developers

Database and application server designers and implementers

Scientific programmers and users with compute-intensive applications

Application developers

System programmers

Each group sees the multicore computer from a somewhat different perspective. Some are concerned with bottom-up methods and need to develop software that takes advantage of hardware-specific and vendor-specific features. For these groups, the more detailed the information about the nooks and crannies of multithreaded processing the better. Other groups are interested in top-down methods. This group does not want to be bothered with the details of concurrent task synchronization or thread safety. This group prefers to use high-level libraries and tools to get the job done. Still other groups need a mix of bottom-up and top-down approaches. This book provides an introduction to the many points of view of multicore programming, covering both bottom-up and top-down approaches.

Multiparadigm Approaches are the Solution

First, we recognize that not every software solution requires multiprocessing or multithreading. Some software solutions are better implemented using sequential programming techniques (even if the target platform is multicore). Our approach is solution and model driven. First, develop the model or solution for the problem. If the solution requires that some instructions, procedures, or tasks need to execute concurrently then determine which the best set of techniques to use are. This approach is in contrast to forcing the solution or model to fit some preselected library or development tool. The technique should follow the solution. Although this book discusses libraries and development tools, it does not advocate any specific vendor library or tool set. Although we include examples that take advantage of particular hardware platforms, we rely on cross-platform approaches. POSIX standard operating system calls and libraries are used. Only features of C++ that are supported by the International C++ standard are used.

We advocate a component approach to the challenges and obstacles found in multiprocessing and multithreading. Our primary objective is to take advantage of framework classes as building blocks for concurrency. The framework classes are supported by object-oriented mutexes, semaphores, pipes, queues, and sockets. The complexity of task synchronization and communication is significantly reduced through the use of interface classes. The control mechanism in our multithreaded and multiprocessing applications is primarily agent driven. This means that the application architectures that you will see in this book support the multiple-paradigm approach to software development.

We use object-oriented programming techniques for component implementation and primarily agent-oriented programming techniques for the control mechanism. The agent-oriented programming ideas are sometimes supported by logic programming techniques. As the number of available cores on the processor increase, software development models will need to rely more on agent-oriented and logic programming. This book includes an introduction to this multiparadigm approach for software development.

Why C++?

There are C++ compilers available for virtually every platform and operating environment. The ANSI American National Standards Institute (ANSI) and International Organization for Standardization (ISO) have defined standards for the C++ language and its library. There are robust open-source implementations as well as commercial implementations of the language. The language has to be widely adopted by researchers, designers, and professional developers around the world. The C++ language has been used to solve problems of all sizes and shapes from device drivers to large-scale industrial applications. The language supports a multiparadigm approach to software development. We can implement Object-Oriented designs, logic programming designs, and agent-oriented designs seamlessly in C++. We can also use structured programming techniques or low-level programming techniques where necessary. This flexibility is exactly what’s needed to take advantage of the new multicore world. Further, C++ compilers provide the software developer with a direct interface to the new features of the multicore processors.

UML Diagrams

Many of the diagrams in this book use the Unified Modeling Language (UML) standard. In particular, activity diagrams, deployment diagrams, class diagrams and state diagrams are used to describe important concurrency architectures and class relationships. Although a knowledge of the UML is not necessary, familiarity is helpful.

Development Environments Supported

The examples in this book were all developed using ISO standard C/C++. This means the examples and programs can be compiled in all the major environments. Only POSIX-compliant operating system calls or libraries are used in the complete programs. Therefore, these programs will be portable to all operating system environments that are POSIX compliant. The examples and programs in this book were tested on the SunFire 2000 with UltraSparc T1 multiprocessor, the Intel Core 2 Duo, the IBM Cell Broadband Engine, and the AMD Dual Core Opteron.

Program Profiles

Most complete programs in the book are accompanied by a program profile. The profile will contain implementation specifics such as headers required, libraries required, compile instructions, and link instructions. The profile also includes a notes section that will contain any special considerations that need to be taken when executing the program. All code is meant for exposition purposes only.

Testing and Code Reliability

Although all examples and applications in this book were tested to ensure correctness, we make no warranties that the programs contained in this book are free of defects or error or are consistent with any particular standard or mechantability, or will meet your requirement for any particular application. They should not be relied upon for solving problems whose incorrect solution could result in injury to person or loss of property. The authors and publishers disclaim all liability for direct or consequential damages resulting from your use of the examples, programs, or applications present in this book.

Conventions

To help you get the most from the text and keep track of what’s happening, we’ve used a number of conventions throughout the book.

Notes, tips, hints, tricks, and asides to the current discussion are offset and placed in italics like this.

As for styles in the text:

We highlight new terms and important words when we introduce them.

We show keyboard strokes like this: Ctrl+A.

We show filenames, URLs, and code within the text like this: persistence.properties.

We present code in two different ways:

We use a monofont type with no highlighting for most code examples.

We use gray highlighting to emphasize code that's particularly important in the

present context.

This book contains both code listings and code examples.

Code listings are complete programs that are runnable. As previously mentioned, in most cases, they will be accompanied with a program profile that tells you the environment the program was written in and gives you a description and the compiling and linking instructions, and so forth.

Code examples are snippets. They do not run as is. They are used to focus on showing how something is called or used, but the code cannot run as seen.

Source Code

As you work through the examples in this book, you may choose either to type in all the code manually or to use the source code files that accompany the book. All of the source code used in this book is available for download at www.wrox.com. Once at the site, simply locate the book’s title (either by using the Search box or by using one of the title lists) and click the Download Code link on the book’s detail page to obtain all the source code for the book.

Because many books have similar titles, you may find it easiest to search by ISBN; this book’s ISBN is 978-0-470-28962-4.

Once you download the code, just decompress it with your favorite decompression tool. Alternately, you can go to the main Wrox code download page at www.wrox.com/dynamic/books/download.aspx to see the code available for this book and all other Wrox books.

Errata

We make every effort to ensure that there are no errors in the text or in the code. However, no one is perfect, and mistakes do occur. If you find an error in one of our books, such as a spelling mistake or faulty piece of code, we would be very grateful for your feedback. By sending in errata, you may save another reader hours of frustration, and at the same time you will be helping us provide even higher-quality information.

To find the errata page for this book, go to www.wrox.com and locate the title using the Search box or one of the title lists. Then, on the book details page, click the Book Errata link. On this page, you can view all errata that has been submitted for this book and posted by Wrox editors. A complete book list including links to each book’s errata is also available at www.wrox.com/misc-pages/booklist.shtml.

If you don’t spot “your” error on the Book Errata page, go to www.wrox.com/contact/techsupport.shtml and complete the form there to send us the error you have found. We’ll check the information and, if appropriate, post a message to the book’s errata page and fix the problem in subsequent editions of the book.

p2p.wrox.com

For author and peer discussion, join the P2P forums at p2p.wrox.com. The forums are a Web-based system for you to post messages relating to Wrox books and related technologies and interact with other readers and technology users. The forums offer a subscription feature to e-mail you topics of interest of your choosing when new posts are made to the forums. Wrox authors, editors, other industry experts, and your fellow readers are present on these forums.

At http://p2p.wrox.com, you will find a number of different forums that will help you not only as you read this book but also as you develop your own applications. To join the forums, just follow these steps:

1. Go to p2p.wrox.com and click the Register link.

2. Read the terms of use and click Agree.

3. Complete the required information to join as well as any optional information you wish to provide and click Submit.

4. You will receive an e-mail with information describing how to verify your account and complete the joining process.

You can read messages in the forums without joining P2P, but in order to post your own messages, you must join.

Once you join, you can post new messages and respond to messages other users post. You can read messages at any time on the Web. If you would like to have new messages from a particular forum e-mailed to you, click the Subscribe to this Forum icon by the forum name in the forum listing.

For more information about how to use the Wrox P2P, be sure to read the P2P FAQs for answers to questions about how the forum software works as well as many common questions specific to P2P and Wrox books. To read the FAQs, click the FAQ link on any P2P page.

Chapter 1

The New Architecture

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?

What Is a Multicore?

A multicore is an architecture design that places multiple processors on a single die (computer chip). Each processor is called a core. As chip capacity increased, placing multiple processors on a single chip became practical. These designs are known as Chip Multiprocessors (CMPs) because they allow for single chip multiprocessing. Multicore is simply a popular name for CMP or single chip multiprocessors. The concept of single chip multiprocessing is not new, and chip manufacturers have been exploring the idea of multiple cores on a uniprocessor since the early 1990s. Recently, the CMP has become the preferred method of improving overall system performance. This is a departure from the approach of increasing the clock frequency or processor speed to achieve gains in overall system performance. Increasing the clock frequency has started to hit its limits in terms of cost-effectiveness. Higher frequency requires more power, making it harder and more expensive to cool the system. This also affects sizing and packaging considerations. So, instead of trying to make the processor faster to gain performance, the response is now just to add more processors. The simple realization that this approach is better has prompted the multicore revolution. Multicore architectures are now center stage in terms of improving overall system performance.

For software developers who are familiar with multiprocessing, multicore development will be familiar. From a logical point of view, there is no real significant difference between programming for multiple processors in separate packages and programming for multiple processors contained in a single package on a single chip. There may be performance differences, however, because the new CMPs are using advances in bus architectures and in connections between processors. In some circumstances, this may cause an application that was originally written for multiple processors to run faster when executed on a CMP. Aside from the potential performance gains, the design and implementation are very similar. We discuss minor differences throughout the book. For developers who are only familiar with sequential programming and single core development, the multicore approach offers many new software development paradigms.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!