ffffiirrss..iinndddd iiii 33//2266//22001122 1122::3366::4444 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 PARALLEL PROGRAMMING WITH INTELØ PARALLEL STUDIO XE FOREWORD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvii (cid:2) PART I AN INTRODUCTION TO PARALLELISM CHAPTER 1 Parallelism Today . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 CHAPTER 2 An Overview of Parallel Studio XE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 CHAPTER 3 Parallel Studio XE for the Impatient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 (cid:2) PART II USING PARALLEL STUDIO XE CHAPTER 4 Producing Optimized Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 CHAPTER 5 Writing Secure Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131 CHAPTER 6 Where to Parallelize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 CHAPTER 7 Implementing Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .181 CHAPTER 8 Checking for Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 CHAPTER 9 Tuning Parallel Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 CHAPTER 10 Parallel Advisor–Driven Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 CHAPTER 11 Debugging Parallel Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .309 CHAPTER 12 Event-Based Analysis with VTune Amplifi er XE . . . . . . . . . . . . . . . . . . . 341 (cid:2) PART III CASE STUDIES CHAPTER 13 The World’s First Sudoku “Thirty-Niner” . . . . . . . . . . . . . . . . . . . . . . . . . 377 CHAPTER 14 Nine Tips to Parallel-Programming Heaven . . . . . . . . . . . . . . . . . . . . . . 397 CHAPTER 15 Parallel Track Fitting in the CERN Collider . . . . . . . . . . . . . . . . . . . . . . . 419 CHAPTER 16 Parallelizing Legacy Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .463 INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 ffffiirrss..iinndddd ii 33//2266//22001122 1122::3366::4444 PPMM ffffiirrss..iinndddd iiii 33//2266//22001122 1122::3366::4444 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 Parallel Programming with IntelØ Parallel Studio XE ffffiirrss..iinndddd iiiiii 33//2266//22001122 1122::3366::4444 PPMM ffffiirrss..iinndddd iivv 33//2266//22001122 1122::3366::4444 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 Parallel Programming with IntelØ Parallel Studio XE Stephen Blair-Chappell Andrew Stokes ffffiirrss..iinndddd vv 33//2266//22001122 1122::3366::4444 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 Parallel Programming with IntelØ Parallel Studio XE Published by John Wiley & Sons, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.com Copyright © 2012 by John Wiley & Sons, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978-0-470-89165-0 ISBN: 978-1-118-22113-6 (ebk) ISBN: 978-1-118-23488-4 (ebk) ISBN: 978-1-118-25954-2 (ebk) Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 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 Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, 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 specifi cally disclaim all warranties, including without limitation warranties of fi tness for a particular purpose. No warranty may be created or extended by sales or pro- motional 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 pub- lisher 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 (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley publishes in a variety of print and electronic formats and by print-on-demand. Some material included with stan- dard print versions of this book may not be included in e-books or in print-on-demand. If this book refers to media such as a CD or DVD that is not included in the version you purchased, you may download this material at http:// booksupport.wiley.com. For more information about Wiley products, visit www.wiley.com. Library of Congress Control Number: 2011945570 Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Programmer to Programmer, and related trade dress are trade- marks or registered trademarks of John Wiley & Sons, Inc. and/or its affi liates, in the United States and other countries, and may not be used without written permission. Intel is a registered trademark of Intel Corporation. All other trade- marks are the property of their respective owners. John Wiley & Sons, Inc., is not associated with any product or vendor mentioned in this book. ffffiirrss..iinndddd vvii 33//2266//22001122 1122::3366::4455 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 ABOUT THE AUTHORS STEPHEN BLAIR-CHAPPELL has been working for Intel in the Software and Services Group (SSG) for the past 15 years. During his time with Intel, Stephen has worked on the compiler team as a devel- oper and, more recently, as a technical consulting engineer helping users make the best use of the Intel software tools. Prior to working with Intel, Stephen was managing director of the UK offi ce of CAD-UL, a German-based compiler and debugger company. During his time at CAD-UL Stephen was primarily responsible for technical support in the UK. Projects he worked on during that time included the design and specifi cation of a graphical linker; the development and teaching of pro- tected mode programming courses to programmers; and support to many varied companies in the telecoms, automotive, and embedded industries. Stephen fi rst studied electronics as a technician at Matthew Boulton Technical College, and later studied Applied Software Engineering at Birmingham City University (BCU), where he also eventu- ally taught. Outside work, Stephen is a regular contributor to the life of his local church, St Martin in the Bull Ring, Birmingham, where he plays the organ, preaches, and leads the occasional service. ANDREW STOKES is a retired lecturer in software and electronics at Birmingham City University (BCU), UK. Prior to lecturing, Andrew was a software developer in the research and commercial fi elds. He fi rst started software development in the 1980s at Cambridge University Engineering Laboratory, where he worked on software for scanning electron microscopes. These software devel- opments continued in the commercial fi eld, where he worked on graphical programs in support of a Finite Element Analysis package. During his time at BCU, Andrew developed many software simulation tools, including programs for artifi cial neural network simulation, CPU simulation, processor design, code development tools, and a PROLOG expert system. Andrew continues these software interests during retirement, with a healthy interest in games programming, such as 3-D chess, where parallel programming is para- mount. Away from computing, Andrew is a keen gardener and particularly likes the vibrant colors of the typical English garden. ffffiirrss..iinndddd vviiii 33//2266//22001122 1122::3366::4466 PPMM Blair-Chappell ffi rs V4 - 03/16/2012 ABOUT THE TECHNICAL EDITORS KITTUR GANESH is a Senior Technical Consulting Engineer at Intel, providing consulting, sup- port, and training for more than 7 years on various software products targeting Intel architecture. Previously, for more than 6 years at Intel, Kittur designed and developed software primarily used for fracturing design data of Intel chips. Prior to joining Intel more than 13 years ago, Kittur was involved in developing commercial software in the EDA industry for more than 10 years. Kittur has a M.S. (Computer Science), M.S. (Industrial Engineering) and a B.S. (Mechanical Engineering). PABLO HALPERN is a Senior Software Engineer at Intel Corporation, working in the parallel runtime libraries group. He is a member of the C++ Standards Committee and helped produce the recent C++11 revision of the standard. Pablo is the author of the well-received book, The C++ Standard Library from Scratch and a coauthor of the paper, Reducers and Other Cilk++ Hyperobjects, which was named best paper at ACM SPAA in 2009. He has more than three decades of experience in the software industry, with expertise in C++, language and compiler design, large-scale development and testing, and network management protocols. During this time, he has developed and taught both beginning and advanced courses on C++ programming. He currently lives in New Hampshire with his wife and two children. ffffiirrss..iinndddd vviiiiii 33//2266//22001122 1122::3366::4466 PPMM