book

Fundamentals of Parallel Multicore Architecture

Name: Fundamentals of Parallel Multicore Architecture
Author: Yan Solihin
ISBN: 9781482211191

by Yan Solihin

November 2015

Intermediate to advanced

494 pages

17h 48m

English

Chapman and Hall/CRC

Read now

Unlock full access

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Table of Contents
Preface
Acknowledgement
About the Author

List of Abbreviations
1 Perspectives on Multicore Architectures
1.1 The Origin of the Multicore Architecture1.1.1 Power Consumption Issue1.2 Perspectives on Parallel Computers1.2.1 Flynn’s Taxonomy of Parallel Computers1.2.2 Classes of MIMD Parallel Computers1.3 Future Multicore Architectures1.4 Exercises
2 Perspectives on Parallel Programming
2.1 Limits on Parallel Program Performance2.2 Parallel Programming Models2.2.1 Comparing Shared Memory and Message Passing Models2.2.2 A Simple Example2.2.3 Other Programming Models2.3 Exercises
3 Shared Memory Parallel Programming
3.1 Steps in Parallel Programming3.2 Dependence Analysis3.2.1 Loop-Level Dependence Analysis3.2.2 Iteration-Space Traversal Graph and Loop-Carried Dependence Graph3.3 Identifying Parallel Tasks in Loop Structures3.3.1 Parallelism between Loop Iterations and DOALL Parallelism3.3.2 DOACROSS: Synchronized Parallelism between Loop Iterations3.3.3 Parallelism Across Statements in a Loop3.3.4 DOPIPE: Parallelism Across Statements of a Loop3.4 Identifying Parallelism at Other Levels3.5 Identifying Parallelism through Algorithm Knowledge3.6 Determining the Scope of Variables3.6.1 Privatization3.6.2 Reduction Variables and Operation3.6.3 Summary of Criteria3.7 Synchronization3.8 Assigning Tasks to Threads3.9 Mapping Threads to Processors3.10 A Brief Introduction to OpenMP3.11 Exercises
4 Parallel Programming for Linked Data Structures
4.1 Parallelization Challenges in LDS4.1.1 Loop-Level Parallelization is Insufficient4.2 Approaches to Parallelization of LDS4.2.1 Parallelizing Computation vs. Traversal4.2.2 Parallelizing Operations on the Data Structure4.3 Parallelization Techniques for Linked Lists4.3.1 Parallelization among Readers4.3.2 Parallelism among LDS Traversals4.3.3 Fine-Grain Lock Approach4.4 The Role of Transactional Memory4.5 Exercises
5 Introduction to Memory Hierarchy Organization
5.1 Motivation for Memory Hierarchy5.2 Basic Architectures of a Cache5.2.1 Placement Policy5.2.2 Replacement Policy5.2.3 Write Policy5.2.4 Inclusion Policy on Multi-Level Caches5.2.5 Unified/Split/Banked Cache Organization and Cache Pipelining5.2.6 Cache Addressing and Translation Lookaside Buffer5.2.7 Non-Blocking Cache5.3 Cache Performance5.3.1 The Power Law of Cache Misses5.3.2 Stack Distance Profile5.3.3 Cache Performance Metrics5.4 Prefetching5.4.1 Stride and Sequential Prefetching5.4.2 Prefetching in Multiprocessor Systems5.5 Cache Design in Multicore Architecture5.6 Physical Cache Organization5.6.1 United Cache Organization5.6.2 Distributed Cache Organization5.6.3 Hybrid United+Distributed Cache Organization5.7 Logical Cache Organization5.7.1 Hashing Function5.7.2 Improving Distance Locality of Shared Cache5.7.3 Capacity Sharing in the Private Cache Organization5.8 Case Studies5.8.1 IBM Power7 Memory Hierarchy5.8.2 Comparing AMD Shanghai and Intel Barcelona’s Memory Hierarchy5.9 Exercises
6 Introduction to Shared Memory Multiprocessors
6.1 The Cache Coherence Problem6.2 Memory Consistency Problem6.3 Synchronization Problem6.4 Exercises
7 Basic Cache Coherence Issues
7.1 Overview7.1.1 Basic Support for Bus-Based Multiprocessors7.2 Cache Coherence in Bus-Based Multiprocessors7.2.1 Coherence Protocol for Write Through Caches7.2.2 MSI Protocol with Write Back Caches7.2.3 MESI Protocol with Write Back Caches7.2.4 MOESI Protocol with Write Back Caches7.2.5 Update-Based Protocol with Write Back Caches7.3 Impact of Cache Design on Cache Coherence Performance7.4 Performance and Other Practical Issues7.4.1 Prefetching and Coherence Misses7.4.2 Multi-Level Caches7.4.3 Snoop Filtering7.5 Broadcast Protocol with Point-to-Point Interconnect7.6 Exercises
8 Hardware Support for Synchronization
8.1 Lock Implementations8.1.1 Evaluating the Performance of Lock Implementations8.1.2 The Need for Atomic Instructions8.1.3 Test and Set Lock8.1.4 Test and Test and Set Lock8.1.5 Load Linked and Store Conditional Lock8.1.6 Ticket Lock8.1.7 Array-Based Queuing Lock8.1.8 Qualitative Comparison of Lock Implementations8.2 Barrier Implementations8.2.1 Sense-Reversing Centralized Barrier8.2.2 Combining Tree Barrier8.2.3 Hardware Barrier Implementation8.3 Transactional Memory8.4 Exercises
9 Memory Consistency Models
9.1 Programmers’ Intuition9.2 Architecture Mechanisms for Ensuring Sequential Consistency9.2.1 Basic SC Implementation on a Bus-Based Multiprocessor9.2.2 Techniques to Improve SC Performance9.3 Relaxed Consistency Models9.3.1 Safety Net9.3.2 Processor Consistency9.3.3 Weak Ordering9.3.4 Release Consistency9.3.5 Lazy Release Consistency9.4 Synchronization in Different Memory Consistency Models9.5 Exercises
10 Advanced Cache Coherence Issues
10.1 Directory Coherence Protocols10.2 Overview of Directory Coherence Protocol10.2.1 Directory Format and Location10.3 Basic Directory Cache Coherence Protocol10.4 Implementation Correctness and Performance10.4.1 Handling Races Due to Out-of-Sync Directory State10.4.2 Handling Races Due to Non-Instantaneous Processing of a Request10.4.3 Write Propagation and Transaction Serialization10.4.4 Synchronization Support10.4.5 Memory Consistency Models10.5 Contemporary Design Issues10.5.1 Dealing with Imprecise Directory Information10.5.2 Granularity of Coherence10.5.3 System Partitioning10.5.4 Accelerating Thread Migration10.6 Exercises
11 Interconnection Network Architecture
11.1 Link, Channel, and Latency11.2 Network Topology11.3 Routing Policies and Algorithms11.4 Router Architecture11.5 Case Study: Alpha 21364 Network Architecture11.6 Multicore Design Issues11.6.1 Contemporary Design Issues11.7 Exercises
12 SIMT Architecture
12.1 SIMT Programming Model12.2 Mapping SIMT Workloads to SIMT Cores12.3 SIMT Core Architecture12.3.1 Scalar ISA12.3.2 SIMDization/Vectorization: Warp Formation12.3.3 Fine-Grain Multithreading (Warp-Level Parallelism)12.3.4 Microarchitecture12.3.5 Pipeline Execution12.3.6 Control Flow Processing12.3.7 Memory Systems12.4 Exercises
13 Ask the Experts
Bibliography
Index

Content preview from Fundamentals of Parallel Multicore Architecture

Parallel Programming for Linked Data Structures

Contents

4.1 Parallelization Challenges in LDS

4.1.1 Loop-Level Parallelization is Insufficient

4.2 Approaches to Parallelization of LDS

4.2.1 Parallelizing Computation vs. Traversal

4.2.2 Parallelizing Operations on the Data Structure

4.3 Parallelization Techniques for Linked Lists

4.3.1 Parallelization among Readers

4.3.2 Parallelism among LDS Traversals

4.3.3 Fine-Grain Lock Approach

4.4 The Role of Transactional Memory

4.5 Exercises

In Chapter 3, we have discussed parallel programming techniques that are applicable for applications that rely on matrices as their data structures. Accesses to a matrix are characterized by a nest of loops in which each loop iterates ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781482211191

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Fundamentals of Parallel Multicore Architecture

by Yan Solihin

Chapter 4

Parallel Programming for Linked Data Structures

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.